Here's the approaches I've used:
1) Resize your disk image to be ~half its current size, and duplicate it.
PRO: Pretty easy, free.
CON: Requires shutting down the server, you lose half of your disk space, and it doesn't protect against catastrophic hardware failure.
2) Use Linode's backup service.
PRO: Pretty easy, works on the fly, doesn't eat into your disk space.
CON: Costs money, doesn't protect against catastrophic datacenter failure.
3) duplicity
PRO: Works well with S3 (and other mechanisms), encrypts the backups, works on the fly, stores your backups in a faraway location, doesn't eat into your disk space.
CON: Comparatively complex to set up, restores will be something you'll want to practice before you need to, churns your disk and network quite a bit.
I also have BackupPC running on a server here (that is, located where I am), but that's probably the most complex of all of these to set up, and it makes noise and produces heat in my domicile, so I'll leave that one off the list.

_________________
Code:
/* TODO: need to add signature to posts */