Prerequisites for WakeOnLan:
$ ether-wake $MACADDRESS
If you add an entry mapping MAC addresses to hostnames to /etc/ethers, you will also be able to simply say
$ ether-wake <hostname>
Some Linux NIC drivers seem to disable the WakeOnLan function of the network card. If you can use WakeOnLan after booting into Windows, but not at all after booting into Linux, your driver is probably one of them. ethtool allows you to change this. An initial query of an interface's properties will look something like this:
$ ethtool eth0 Settings for eth0: Supports Wake-on: g Wake-on: d Link detected: yes
$ ethtool -s eth0 wol g
This time, a query to confirm the result should produce something like this output:
$ ethtool eth0 Settings for eth0: Supports Wake-on: g Wake-on: g Link detected: yes
Note that you'll need to change the setting anew on every boot, so stick the command in rc.local or whichever boot script is applicable.
If you encounter further problems check the parameters passed to the halt command in your shutdown script (/etc/init.d/shutdown.sh on gentoo). The -i parameter tells halt to down all the network interfaces just before shutdown which will prevent wol from working.
First of all, you normally use ether-wake to trigger a wake-on-lan event on a powered off computer. It is unlikely to have a firewall running at this point!.
ether-wake works by sending a special ethernet frame. Read the notes at MagicPacket for more information about this. Because this is an ethernet frame, and not actually an IP packet, it is not routable. The answer to the above question is "You can't".