Update (2011-12-10): I updated this article to make it a bit more clear and confirmed it works exactly the same on Linode.
Update (2014-09-21): Just a note that I've used this successfully on several times on Digital Ocean.
This is a step by step I used to set up SSH and lock down access on my Rackspace Cloud VPS running Ubuntu Server 10.04. There's a good chance this will work for other server providers and possibly other versions of Ubuntu. (But no guarantees.)