On Lion, you can use tmutil to clean things up properly.
To delete backups one by one (snapshot by snapshot).
sudo tmutil delete /Volumes/drive_name/Backups.backupdb/mac_name/YYYY-MM-DD-hhmmss
If you are sure you have selected the correct path, you can delete all backups from that one Mac by not passing in the time and letting it delete the entire folder:
sudo tmutil delete /Volumes/drive_name/Backups.backupdb/mac_name
The sudo command needs your password (and it won't echo to the screen, so just type it and pause to be sure you're dating the correct files before pressing enter).
Both are feasible. I use the first myself, and my sister had the second set up at one point.
1) On the laptop, you can install netatalk which handles AFP file sharing. Time Machine requires some special AFP features but those are supported by the version of netatalk that comes with Ubuntu 12.04 (just do sudo apt-get install netatalk).
Here's a decent guide for that, although with current versions you shouldn't actually need avahi-daemon, netatalk can handle Bonjour by itself now. You may actually just be able to get away with adding a line like:
/home/username/backup "Time Machine" allow:username options:tm,noadouble
to /etc/init.d/netatalk/AppleVolumes.default, which is all I had to do on one machine running 12.04 (I don't remember having to do the other stuff, but YMMV).
Note that you should NOT ever need to use the "EnableUnsupportedVolumes" hack as netatalk meets Apple's spec and should appear as a backup destination automatically. Using this hack causes Time Machine to ignore problems that can cause loss of your backups.
2) A Time Capsule can indeed be connected to a wireless network as a client to share the hard drive (it can also share a printer connected via USB). I think the setup wizard makes it pretty easy, you're basically just looking to set it up as a wireless client and not a router. You might want to hook it up by ethernet if the signal isn't so great, though.
If 320GB is enough space (which I imagine it is, unless your Air has a 512GB SSD), I'd go with the netatalk solution unless money is no object.
Best Answer
Just Just go into
System Preferences…Time Machineand hitSelect Disk…(If that's not working, let us know what error you're getting/what does happen.)