Of course a huge advantage of a networked Time Machine (aka Time Capsule) is you don't need to be plugged in, and you don't need to even think about it. I'm not going to duplicate Dan's excellent guide but instead provide commentary. The apt-get upgrade took quite a while, > 1 hour, but I'm not sure exactly since I gave up and went to bed. I guess I had fallen a bit behind on updates.
The gparted application requires a UI. I have a monitor/keyboard for the RPi but didn't want to monkey around with the keyboard/mouse/hdmi nonsense so instead I connected via an X Window session, only this didn't not work. I tried ssh -X pi@host and lxsession but nothing happened. Turns out you need to install xquartz. I found it a bit odd that this wasn't mentioned by the vast majority of posts on the forum.
Now I could connect and launch gparted (from the start menu under "preferences"). With gparted I deleted the existing partitions and created two partitions (timemachine and data). This is a 2TB drive and while I read that the ideal Time Machine drive size is 2-3x your hard drive size, I went with a slightly smaller 1TB. I chose ext4 for the filesystem. I figured that since Google picked ext4, and Google knows a thing or two about filesystems, it's probably a safe bet. At first I tried resizing the existing partitions but quickly realized this was a horrible idea as it was copying byte-by-byte useless data from one partition to another. I went through a few iterations with gparted and found gparted worked best when I applied changes after each change (ie not batching). With multiple partitions you should have an sda1 and sda2; take note of this when mounting drives. Oh and I just ignored the "Daemon is inhibited" error.
As others have noted, the appending to fstab results in a permissions error so instead sudo with vi or nano and append the line. At some point during the installation the permissions to the mount got whacked so I again ran sudo chmod 777 /mnt/timemachine/
Then, I created a user for Time Machine:
useradd timemachinepasswd timemachine
Now under Time Machine preferences, select disk, I see the raspberry pi disk. I did the initial backup via ethernet and it took about 10 hours for 144GB.
I have an old dell desktop which I could just have easily used for Time Machine but it consumes about 70W and makes lots of unpleasant whirring noises. The RPi and USB hard drive only uses about 8-9 watts, as measured with my kill-a-watt! Of course the hard drive uses the lions share of power, about 7 watts.
So far I'm quite pleased with this setup. The total cost came to a very reasonable $102 ($40 Pi + $20 USB + *$30 HD + $12 SD Card/Power *I got a super deal on the hard drive). The setup could have been about 20 minutes but I spent about an hour, most of which was spent figuring out the X Window snag.