I run an ubuntu server in the basement and have a disk shared from there that our (wife and I) macbooks use to back up via time machine over the wireless network.
http://www.kremalicious.com/2008/06/ubuntu-as-mac-file-server-and-time-machine-volume/
We used to use usb hard drives but were never consistent; with the network backups its seamless. Next week I am going to replace the single disk with a mirrored array just to be extra safe.