Please note: This guide assumes you are using Snow Leopard. For Lion, things are a little different. I’m writing a new guide with Lion in mind but I haven’t got round to finishing it yet – the short version is: you need Netatalk 2.2 with its Avahi support built-in, and remove any manual Avahi service files you have created.
There are many guides on the Internet that deal with getting Apple’s Time Machine to back up to a network disk, however all of those that I managed to find rely on setting a hidden system preference to show unsupported disks – and hence don’t help with the problem of restoring from backup should the worst happen.
There is a way, though, to get Time Machine backing up to a Linux server without jumping through any hoops on the client. The backup volume just appears in the Time Machine preference pane, and the Mac OS X Install DVD’s restore mode also can see and restore from the network volume.