Well, first of all I mistakenly assumed our VPS backups would be sufficient, but the first step is actually dumping the database every interval you'd like. If you don't dump it, you might end up with a corrupt database should you be relying on the VPS backups.

Then, we set up a process to zip the database dump and send it off to tarsnap. We delete the backup done 30 days ago each time we run.

It works fine for us, but I much prefer using Heroku and not having to worry about it :)