Ksplice. Available in the Ubuntu Universe repository since Karmic (October 2009).
I've been fantasizing about this for years.
One of the things that has always been nice about Linux has been how much less often it needs to be rebooted for things like software installation and upgrades. But it has still needed to be rebooted for occasional security fixes for the operating system itself - the kernel.
Now it doesn't.
"An evaluation against Linux kernel security patches from May 2005 to May 2008 found that Ksplice was able to apply all of the 64 significant kernel vulnerabilities discovered in that interval."( Read more... )
Update 2010-12-21: It says it updated my kernel on both my home computer and (linode) virtual server.