Install afpfs-ng, I installed version 0.8.1 from source using the following directions (I found some old instructions here, but there is a typo so I have adjusted it to match the INSTALL instruction that came with the source files.)
Install the dependencies
sudo apt-get install lbgcrypt-dev libgmap-dev readline-dev libfuse-dev
Unzip the tar.bz2 file, cd into the resulting folder, build and install
tar -xfz afpfs-ng-0.8.1.tar.bz2
sudo make install
It appears that they actually have a .deb file too, see here, but I didn't notice it until I started typing this response.
After installing you can then mount an afp share from the command line, its not quite as nice as just putting
afp://share into nautilus, but certainly better than nothing. Mount using
afp_client mount -u <user_name> -p <password> <server>:<volume> <mountpoint>
<mountpoint> is a folder that the current user has read and write permissions. If you use
password you will be asked for the password interactively, like when you use
sudo. I highly recommend this, otherwise your password will be displayed on your screen in plain text. After all of that, the mount should appear in your nautilus side bar.
When you are done and wish to unmount the share, you can not use the eject button that is displayed in nautilus. Instead use the following command
afp_client unmount <mountpoint>
If you like using the command line, then there is also the command
afpcmd that behaves like a command line ftp client.