I like rsync.net - A great RSYNC service ran by geeks.
The next step is to determine what you need to backup. I assume you're hosting some kind of website. In the ideal world, you'll have an up-to-date SVN repo of your actual application code, so, you probably only need to backup any 'uploads' directory, and your database.
You need to determine an adequate policy for your DB dumps. You may be lucky that your data doesn't change that often and you can make nightly backups, or, bi-daily backups. If your data is changing a lot, you may need to run dumps more often. DB backups (we'll assume you're using MySQL) can often lead to locking problems, whereby the amount of time taken to dump your data impacts on the running of your site. If you have this problem, you might want to consider your backup strategy very carefully.
It's also worth backing up /etc - It's usually quite small in size, so it's worth getting the full directory. In here will usually be your webserver configs / mail configs / firewall configs / user accoutns. I would never suggest recovering the whole directory, but, it's worth having a reference of what your settings are. You probably only need to back this up when you make a change.
It may not be appropriate in your case, but, I also backup /home.
You also should backup your CRON jobs; it's a nightmare trying to re-create these if you don't have a good list of what you need to run and when.
I'd start by backing all of those items into a single directory /var/serverbackups then, when that backup job has finished, rsync the whole tree to an external service like rsync.net or one that has already been mentioned.
It just means you're able to change the off-site location more easily if you need to in the future.
If you want a more hand-holding approach, backup2l is a Debian app that you can install that will handle the backup creation based on a string of paths you provide; it will managed differential backups to tar.gz and handle selective recovery. You can still rsync the backup2l target directory once it's complete.