Start with the good tutorial here: HowTo: Make Ubuntu A Perfect Mac File Server and Time Machine volume - even when you are running a different Linux distribution.
In this tutorial you learn how to set up afp shares and avahi, an opensource implementation of Apple's Bonjour to announce the afp and TimeMachine services across the network.
Then when you have afp and avahi running, switch to this tutorial: Set up Time Machine on networked AFP volume System 10.6
Create the sparsebundle file locally, or on a external harddisk, not directly on the network share
Save the edited plist file as plaintext ascii. This was the missing link for me, look up the UUID in System Profiler and put it in the plist file
After copying the plist file, unmount the sparsebundle before copying it to the network share
Be sure you are connected to the AFP share, not to a Samba or other share on the same server
Was this article useful to you? Please help me by using the toolbar below to tweet the article, give it an eKudo or add it to Hyves, Facebook, Delicous, Digg or another site. Thanks!