If you have a lot of space, the easiest way to go about things is to probably just make some huge gzipped tarballs of your partitions. This will copy on the data within them. For instance if you had 3 partitions, /usr, /boot, and /home (excluding swap):
tar czvf home.tar.gz /home
With all three, this of course would stick the end created file in whatever directory you were currently in, so make certain there is room. Burn these to CD once a week, whatever, possibly copy them to another machine, or both.
In the event of a fullblown system meltdown, repartition the drive to the correct size, boot with something like tomsrtbt, copy the tarballs on there (mount the cd, nfs, whathaveyou), untar them, and then as long as things like /dev/hda1 stayed /dev/hda1 and such, just re-run lilo. Its pretty easy.
Although really I just backup all the .conf files and such that aren't still at defaults: httpd.conf, proftpd.conf, the mail spool, etc, and back them up to /home that then gets gzipped up on a cronjob once a day and copied over to a few different machines. In the case of a meltdown I just pick out distro X, install it, and then untar home and monkey about with the .conf files for a little while.