I have just installed Areca on my Windows Vista machine, it is a platform independent (Java based) backup solution. I haven't (yet) tried the Linux version, but fully intend to. It works by doing incremental backups of specified folders, which you can then schedule using cron.
As for exactly which files to backup, that would depend entirely on your system.
If you're using all open source/free software, then you needn't backup the programs themselves, but to save time on downloading, it may be worth your while to backup the install files, in case you have to reformat your HDD or something.
Most of your settings are probably contained within your home folder, though you may have customised some more general things. In most systems that I have worked with, any settings not contained in your home folder are contained in files in a folder called "/etc".
Since Linux (and also Mac, I believe) uses config files in preference to a central registry, backing up these settings is a simple matter of backing up the relevant files. Make sure you do back up your entire home folder though!
Also, though I haven't checked it out other than a passing glance, there is "flyback" available from Google Code:
This is modelled on Time Machine and the screenshots look pretty
Hope this helps.
Also, in future posts, it would be worth mentioning, amongst other things, which distribution (distro) you are using, as it will help people to work out the best solution to your problem.
For example, if you are using Ubuntu or Debian, then the program downloads will be in one specific place (usually "/var/cache/apt/archives").