I started using Tarsnap to backup my personal server "to the cloud". I found it was quick to set up, easy to learn, and works pretty well.
And, yes, I've already made a wiki page that documents how my monthly restore tests will be done. The data is encrypted, which means if you lose your crypto key you can't get your data back so my restore test is done from a different machine to force me to have a copy of the key stored safely off-line.
If you are looking to do backups over the internet, check this out.