It turns out there is a fairly good guide for this at Ultimate Guide to Configuring Samba for Time Machine Backups on Debian Servers. However, it is missing one critical step. One also needs ea support = yes in the [Global] section. Once I added that, the following configuration works:

[Global]
...
# MacOS compatibility                                                                                                                  
ea support = yes
security = user
wide links = yes
unix extensions = no
vfs object = acl_xattr catia fruit streams_xattr
fruit:nfc_aces = no
fruit:aapl = yes
fruit:model = MacSamba
fruit:posix_rename = yes
fruit:metadata = stream
fruit:delete_empty_adfiles = yes
fruit:veto_appledouble = no
spotlight = yes

[TIMEMACHINEBACKUPS]
comment = Time Machine Backups
path = /tmbackups
available = yes
writable = yes
guest ok = no
valid users = samba
browsable = yes
vfs objects = catia fruit streams_xattr
fruit:time machine = yes
fruit:time machine max size = 9T

Of course, modify path and max size to your setup and share name and user as desired.

I've used rsnapshot to excellent effect. You can have it rsync and keep as many old versions, based on time as you want/have space for. I've got 6 potential versions of things from today, daily for a week, 4 weeks, and then 6 months worth. I've already used it to recover several file I thought I'd lost due to overwriting.

The only problems I have had was it not running due to the previous run not completing in time, and so it left the lockfile dangling. This was on a remote machine that did password-less logins over SSH to rsync files off for backup/archive and I didn't log in very often to the server to check it. Running a logwatch script on there (emailing problems from the logs) at least made sure I saw the problems to restart it, and it's been hassle free ever since. On my local server, it's been no problem at all.

This answer explains things for a Windows-based server, but it should work fine for Ubuntu.

1. In Terminal, type the following command:

   defaults write com.apple.systempreferences TMShowUnsupportedNetworkVolumes 1

2. Now, as long as you have a connection to your computer’s shared drive, you should be able to see it in Time Machine.

3. To connect to that shared drive: Finder > Go > Connect to Server.

4. Type in the IP address or host name of the server. You may be prompted to log in.

5. Configure Time Machine to use the drive, and try creating a backup.

6. Time Machine will try to create a “sparse bundle” on the drive, and will fail.

7. Open Console and check system.log. You will see the name of the file Time Machine was trying to create. The name of the file will be something like .MacBook Pro_00254bd7abe8.sparsebundle

8. You will need to create a sparse bundle with this name and put it on the hard drive manually before the backups will work. To do this, open Disk Utility.

9. Click New Image > Set image format as “sparse bundle disk image” > Set partition map to “no partition map” > Set the size as the maximum size you are willing to allot to Time Machine. Don’t modify anything else.

10. Though the file on the hard drive will need to begin with a period, you will not be able to do this right away through Disk Utility, so just call it whatever you want right now.

11. You can rename the file so that it has a period before its name from Terminal on OS X or Ubuntu. Your final name should be like .MacBook Pro_00254bd7abe8.sparsebundle.

12. If everything is done right, you should now be able to use Time Machine with an Ubuntu Server.

Note: This answer was copied from MacRumors and has been formatted for AskDifferent. I’ve used this method myself, albeit on a Windows shared drive.