Recommend Keylogger for Ubuntu
I'm interested in increasing my chances of recovering the machine in the event that it's ever stolen.
I like Rory's answer. However, I think there are three risks involved here: the risk of losing your hardware, and the risk of losing your data, and the risk of your private data being exposed. Solutions which attempt to recover the machine are only solving one risk.
The risk of data loss can be mitigated by a good data backup system.
The risk of data exposure may be mitigate by good data protection: proper access controls, solid encryption, and good keys or passwords. The risk of data exposure may also be mitigate by destruction: remote wiping, conditional wiping, timed expiration. The final risk is the loss of your hardware.
When you have risk there are three options: mitigate the risk, assume the risk, and transfer the risk. You have already thought of some way to mitigate the risk of theft. However, you haven't covered a few of the most effective, which tend to be operation rather than technical.
Never leave your laptop unattended. If a thief has no opportunity, they can not steal your laptop.
When you are not using your laptop store it securely. At least use a locking cable attached to something unmovable. Or keep it in a locked drawer or cabinet. If you are not in a familiar place you can lock it in the trunk of your car.
Mark your laptop with your name in a way that is difficult to remove. You can have it etched into the case, or failing that large letters in permanent marker. It makes it harder for a thief to sell Chris's laptop, and if you put contact information as well it will help get it returned if you lose it.
Another way to deal with risk is assuming the risk, but I don't recommend doing that.
The final way to deal with risk is to transfer it. This is usually done by buying insurance. You can buy laptop theft insurance to cover the value of your laptop. If this is a personal laptop and you have homeowners insurance you may already be covered under personal property, or you may be able to add coverage to an existing policy for a small fee. I don't know insurance very well but I think renters insurance may act similarly to homeowners insurance. In any case you can check with your insurance agent.
I would go with LKL myself, but that is very subjective - others will prefer something else, I'm sure.
It doesn't matter whether or not it is in a repository, in fact I would want to build something like that myself from source.
There is of course a risk with having a keylogger installed - it could be used against you!