Backing up your home directory is very essential, and the cream is not just the data that you save out there, but the milestones that keep track of how your data changes over time. That is what actually gets you the best possible data restore. Oh! and don't get me wrong, I am not talking about keeping track of your deleted impressive movie collection or mp3s; there are a tons of ways to handle them. If you are not getting my idea, think emails, think resumes, think an article you have been working on and also think of a lot of other useful things that you could possibly imagine. We are talking about a typical home directory here which can be quite a number of gigs.
Hosting companies that provide VPS services are a good idea but their services primarily suit websites (or probably small projects). So, they are a big no-no. You don't want to pay a bomb for data back up ? Do you ? You would rather be happy getting a portable disk which probably is one more good option. But my concern here is not just backing up and versioning it but doing it somewhere that is reliable and has minimal chances of getting screwed up (If your computer's hard drive can give up, so can a portable hard drive!).
The storage solution: Amazon's cloud computing has been doing the rounds and that made me try out their simple storage service (Amazon S3). Not only is it very cheap, it's quite reliable (atleast for my needs): data is encrypted and is stored over multiple locations in a distributed network. But there's one caveat though, this is not your normal home computer filesystem. There's a lot of caching and stuff like that going on and you will end up seeing things that are unexpected. On a Linux machine, the best thing to try out is Jungledisk (not open source) that sits on top of FUSE.
Version Control: Ok, I started straight away looking for distributed version control. I just didn't want to get into the cumbersomeness of a central repository based software to track my home directory. The first look I had was on mecurial. Pretty impressive. Well, remember about the unexpected things I was talking about above, that screws up Mercurial and you end up having corrupt clones quite often or if you manage to get it clean, you will eventually screw it up during a push of changes.
The next in my list was Bazaar. That's a cheesy name ;) Well, trust me, it does what its supposed to do and it certainly scores on features and the best of all, it gives me clean merges and pushes. No more corruptions. How much it costs: Well, the only thing you pay for is Amazon's storage service which is really very cheap compared to other methods which anyways do not fall into the category of competition.
Anything else: Bazaar has got a nifty plugin architecture to plug in python modules that would make your job easier. A plugin that automates the process of adding newly created files and committing and pushing changes to the backup would be a really cool thing to do.