This guide will walk you through installing and configuring AFP in Ubuntu. If everything goes well, your Apple computers will be able to connect (and backup with Time Machine) to the server without issue.
This article combines steps from other articles and updated to reflect the latest version of Netatalk (AFP), Mac OS X (Mountain Lion) and Ubuntu 12.04. These general steps can work for other distributions of Linux but have not yet been tested. In Ubuntu, there is no need to manually open ports in the firewall.