After many mentions on LifeHacker and at work (thanks Mike!) I've decided to set up all my systems with the Prey project
This website and open source application allows you to register up to three devices for free, which check in to the website at regular intervals to verify they're still where they should be. The moment you notice them missing (or stolen) you can mark that device as missing, and then the next time prey checks in, it'll be activated.
Prey can be configured to send emails, take screenshots, lock your system, and best of all, use nearby WiFi and geolocation to work out its location. Read How I got my stolen laptop back within 24 hours to see it in action.
The free version offers support for three devices, which is just right for me (desktop, netbook and android phone) and supports most common operating systems, including (crucially for me) Linux. You can pay for more devices and more features if you need to.
Set up on Android was dead easy, just download it from the market and enter your Prey username and password. My two Debian Linux machines were slightly more tricky.
I run Debian testing on my desktop machine, and prey was in the repositories (apt-get install prey), but it seems to install it in /usr/lib rather than /usr/share (as the website says). It also doesn't automatically set up the cron job that checks in every 20 mins. My Crunchbang (Debian based) EEEPC netbook didn't have it the repos, so I had to download it from the website and unzip it to /usr/share/prey.
The command to install the cron job is in the README file (which I didn't read first), however everywhere in the documentation and the website seems to talk about an "installer". I'm guessing that the installer is in the windows version (and possibly MacOS and Ubuntu) but I certainly can't find it in the vanilla Linux installer. You therefore have to figure out what to put in /usr/share/prey/config and then ignore the warnings and create the device manually in the control panel on the website.
The API Key is (fairly) easy to find under the "Account" section of the website, but it took me a while to figure out that the Device Key is the bit in the url (e.g. the abcd12 in http://panel.preyproject.com/devices/abcd12) and NOT the name that you give the device when you set it up. I'm sure if I was able to find the GUI installer that'd all be set up for me, but it's a shame that the instructions on the site seem to depend on this being there and they seem to ignore the manual set up route.
I'm still not sure if I've got all the config right, but at least the devices are reporting OK on the website and there's no errors in the logs. Some more testing is needed to make sure it'll all work if I pretend it's been stolen.
So, I've spent a few hours setting up something I hope never to have to use, but I think it's worth it for the peace of mind.