I have a new MacBook Pro that I want to be able to log into through ssh or vnc, but no matter what combination of things I try nothing seems to work. Even tried LogMeIn
How do I set-up my MacBook so that I can remote into it, even if it's asleep
You can't forward the magic packet. It works on Layer 2 of the OSI model and is addressed to the MAC address (ethernet ID) of the target computer, which knows nothing about Layer 3 (IP, i.e. The Internet). This is why it's called Wake-on-LAN.
What you can do is install software on your router that can send a magic packet for you to the machine in question after you log into the router. I do this with a WRT54GL running the Tomato Firmware. I'm sure it could also be accomplished with DD-WRT.
To answer the rest of your question, most people using remote login software just don't bother with sleep in the first place. But regardless, I routinely use OS X's built-in Screen Sharing, which is basically VNC with enhanced authentication. Others commonly use 3rd party VNC clients and servers, like Vine server (Or, they just open up the Screen Sharing/Remote Desktop server to less secure VNC connections). These all require that the appropriate ports be forwarded from your router.
A more user-friendly approach is the 3rd party TeamViewer, which is fairly polished, free for personal use, and doesn't require port forwarding since the "server" computer actually logs into one of TeamViewer's servers from behind your network to wait for a "client" connection.
I have gotten it to work:
After a couple of seconds, the machine is up, and I can eg. log in using SSH.
I have a Zyxel P-2602HW-D1A router and a Macbook running OS X 10.7 (Lion).
I have yet to find a command line tool for Mac/Unix that can do WOL over the internet (ie. specifying both MAC address and IP), but there is a tool for Windows here: http://www.matcode.com/wol.htm
Why not just forward a port on the router that you probably have? In this setup, your router would have the static external IP (or use some dynamic DNS service), the router would forward any traffic to one of its ports to your server (which should have a static IP inside your LAN) or it could forward it to a broadcast address of your LAN.
Now sending the the WOL package to your routers IP & the specific forwarded port should start your server (because inside the WOL package there's the MAC of your server).
Port forwarding is pretty common feature in routers, so there should be no need for fancy firmware hacks/WOL capable routers.
These seeem to support my idea:
If you have a TimeCapsule then you can do this in theory. When a Mac goes to sleep it sends a message to a "Sleep Proxy" advertising what services it can offer it is woken up. The Time Capsule then takes care of waking the MacBook, even over wireless.
See: http://support.apple.com/kb/HT3774 which also says this works for Back To My Mac.