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.
I asked the same question on the Apple forums, and got a solution that worked for me:
https://discussions.apple.com/message/20182532?ac_cid=op123456#20182532
I'll repeat it here so somebody else might find it useful in the future:
This is where you use a roaming network.
Do not extend.. that is much slower.. since you have ethernet and the TC plugged in you are 90% of the way there.
Use the TC to create a network.. with the same name and same passkey with security settings as the wireless downstairs. Locking channels is not a bad idea.. as this does require one difference .. the network upstairs must be on a different channel to the one downstairs.. then all will be hunky dorey.. !!
Best Answer
Time Capsule is actually just an AFP host. You can configure any device that serves the AFP protocol to be a Time Machine backup destination.
However, if the device does not support AFP, it takes some work on the client to get TM to use it as a destination.
You can see the results of that question here: Time Machine over SMB/CIFS share?