I have a cron job that dumps the databases into a directory with a time-stamped name. The last few regular nightly back-ups are kept, then weekly for a couple of weeks, then monthly for about a year. The parent directory is then backed up to S3 using duplicity. I've done other, cleverer things in the past with rotating through buckets based on the month, keeping every backup, doing them twice a day, that sort of thing.
I test recovery by spinning up another server, running the scripts to bring it up to production status, and running the script that uses duplicity to pull the data dump directory back out of S3, and then restores the database from the dump.
At $0.15 a gig to store data, and about $0.10 a gig to transfer it in, the cost of S3 is pretty much just noise. I've got on-disk dumps of my database if the database is corrupted on my machine, and I've got back-ups of those dumps if I need them.
Duplicity is pretty fantastic -- definitely check it out.