A few months ago, I explained how to setup Time Machine to auto-mount over AFP to a remote server. This process still works for me, but I would like to note that there is an easier method to try first.

Open the Time Machine preference pane in System Preferences, and click “Select Disk…”. Select your network share. Done.

I am not sure why this did not work for me last year, but I did switch my remote server to use Netatalk 2.2.2 for Ubuntu.