December 2015: I just wanted to note that the solution below stopped working for me after a while. However I recently purchased a Synology NAS and configuring as a Time Machine backup destination is fairly easy.
I just got a MacBook Air and had already read about how you can setup your own network based Time Machine backup on a Linux server. The problem is that there is some outdated information floating around, which caused me some headaches getting it to work with errors such as “The network backup disk does not support the required AFP features” and “backup failed with error 45” (in Console).
First: you need version 2.2.x of the “netatalk” package. Debian 6.0 (Squeeze) comes with 2.1 by default, which won’t work (with Mac OS X 10.8 “Mountain Lion” at least). Second, lots of how-to information includes instructions on creating a /etc/avahi/services/afpd.service file. With netatalk 2.2, this file is redundant: you do not need to create it.
Back to netatalk. Really old information will talk about needing to compile it from source to have it support the required authentication protocol. That is no longer relevant with the most recent version. If you are still running Debian 6.0 (still the stable version at time of writing) you can get netatalk 2.2 from Debian 7.0 (Wheezy) by doing the following (all as root): first add the following line to /etc/apt/sources.list
deb-src http://http.debian.net/debian wheezy main contrib non-free
Then run the following commands:
aptitude update apt-get build-dep netatalk apt-get -b source netatalk dpkg -i netatalk_2.2.2-1_amd64.deb
Change the filename accordingly if the version number has slightly changed. With netatalk 2.2 installed, follow other guides on the net (such as this one or this one) to configure a Time Machine AFP share on your Debian server.