What's the current infrastructure? Do you have a dedicated server, or some smaller VPS's? I manage a few dedicated servers that get resold as VPS servers, and if you'd like to talk infrastructures I'd be happy to help.

Backups depend entirely on the type of service you're running on, but Rsync is a good idea as well.

If you just have some application data that you are looking to back up, it is pretty straight forward to back stuff up to Amazon's S3 or glacier (depending on your usage of said backups). Storage is relatively cheap and the amazon api is pretty when using either s3cmd or boto.

I'm on Linode and just take advantage of their backup service (https://www.linode.com/backups/). It's pretty much just set it and forget it.

I do the same, but I like to have an external backup as well. What if Linode disappears and you need to rebuild on another hosting provider? Small chance I know, but multiple backups never hurt.

The simplest solution is to simply rsync the VPS (or just the important data) onto another storage device to which you have access.

I rsync to another server which is backed up via CrashPlan.