I recently got a MacBook Pro and wanted to use it's Time Machine functionality. The only large hard drive I had was in my desktop computer dual booting Windows 7 and Ubuntu - so I decided to add an AFP server to Ubuntu to make it act like a Time Machine server.
I originally tried using NFS and Samba, but the setup procedure turned out to be too complicated and neither of them worked out in the end, for some reason (but I'm sure it could be done). I stumbled across netatalk which includes an AFP (apple file sharing protocol) server. I then followed the tutorial here, to set it up.
However, some things to note:
The tutorial is a year old and the latest version of netatalk has not been uploaded to the ubuntu repositories, so you need to get the latest sources from the netatalk website and compile them yourself (the latest version has Time Machine support).
You can follow the tutorial through, like I did, and just update to the latest netatalk when you've completed the tutorial. Simply download the latest netatalk sources, do a ./configure, make, sudo make install and reconfigure the netatalk configuration files. Make sure to add the "tm" option to the configuration files. I posted a comment on that site, so just search the page for the user "solarwind" to see my comment about that.