This special packet, called a magic packet, carries a special "signature." When the network interface sees this signature, it recognizes this as a wakeup call.
The MAC address is a unique "hardware" address typically burned into the network interface by the equipment manufacturer. It is nromally used for layer 2 packet delivery, to ensure that only the correct host receives and opens a packet. Normally it is included in a special "header" area of the packet, but in this case it is being used in the data area.
For more information on MAC addresses and how they are used in layer 2 routing and switching, see Part 3 of my TCP/IP FAQ on this site.
The most common scenario in which you are likely to encounter Wake On LAN is in a network using IP for routing and Ethernet switches to create LAN segments. Your target machine will be plugged into an Ethernet switch. In this case, you simply send the "magic packet" containing the target's MAC address in the data area (16 times, remember?) to the multicast address of the subnet in which the machine normally lives.
A multicast packet is kind of like a broadcast. However instead of sending a packet with a destination IP address of 255.255.255.255, you send it to the broadcast address of the subnet. Let's say you have a segment using the class C network 192.168.1.0. The broadcast address of this subnet is 192.168.1.255 - that's what you use as the destination IP address on the packet. This packet will be delivered (usually) by any intervening routers to the Ethernet switch that comprises the network segment. The switch will treat it like a broadcast, copying it to every port on the switch. Your target machine will see the packet, discard the headers, recognize the data "signature" and wake up.
The reason we want a multicast packet as opposed to a broadcast to 255.255.255.255 is that many routers (most) will not pass broadcast packets unless specially configured to do so. In fact, that is one of the advantages of using routers to break up network segments - they prevents broadcast "storms" by simply refusing to pass broadcasts. But multicasts are usually okay as they are simply delivered as a single packet all the way to the target network segment.
If your Ethernet segment is created by a hub rather than a switch, it gets even easier - the hub ALWAYS copies EVERY packet to EVERY port anyway.
If you are sending the magic packet from a machine on the same subnet as the target device (i.e., you don't have to pass through a router to get from point A to point B), your machine will first attempt to learn the MAC address of the device using something called ARP - Addres Resolution Protocol. You'll basically be sending out a packet asking for the MAC address of the device with the IP address in question. Since the device is powered off an can't answer, your machine will simply refuse to send the packet.
If you are on a different network segment, there is a little more hope (but not much). Your packet will make it all the way to the router servicing the target machine's segment before it dies. That router will have the same problem your own computer would have if you were on the same segment - it will try to ARP for the MAC address of the machine, and failing to receive an answer will drop the packet.
You CAN force the router to deliver it - by placing a static route on the router FORCING the router to dump the packet out the appropriate interface - but static routes are something we try to avoid in big networks, especially static routes to individual hosts. They make the router's configuration a lot more complicated, and that's a "Bad Thing."®