I've been using Back In Time for some time now. It works well and has been very stable. I thought it would choke when my external backup drive was plugged out, but it handles such circumstances well.

It creates hard links (just like Apple's Time Machine I believe), which means that snapshots can be quite small.

Yet more howtoforge spam...

joschi is a bot, see http://news.ycombinator.com/submitted?id=joschi (and not a single comment to go with them...)