I've never used a VNC/Remote Desktop client before, so I need a "beginners guide". I want to connect to my Mac that is at home from another Mac or from Ubuntu Linux. What do I need to do in order to do this? Does my Mac at home have to be turned on all the time? Or is there a way to connect to it while it's turned off (i.e. wake up on request or something like that).
I can't answer the question about "Wake on LAN" on your home machine, but you would most likely do best to solve this while the machine is running before you attempt to do so while the computer is sleeping.
VNC is pretty basic, you simply need to install software to control the server (machine you want to connect to), and the client (machine you connect from). This is typically the same download and it provides both features.
For Mac I find this wikihow article, http://www.wikihow.com/Setup-VNC-on-Mac-OS-X
On Ubuntu, there is a built in VNC client under Applications > Internet > Remote Desktop Viewer.
Make sure the server is up and running first before you attempt to connect with the client.
You will need to forward ports (NAT) on your router if accessing across the web, assuming this is what you are wanting to do.