So after isntalling a fresh copy of Ubuntu today, I try:

r00t@r00t-laptop:~$ sudo apt-get install openssh-server
Reading package lists… Done
Building dependency tree
Reading state information… Done
Package openssh-server is not available, but is referred to by another package.
This may mean that the package is missing, has been obsoleted, or
is only available from another source
E: Package openssh-server has no installation candidate

No big deal, lets look up how to fix this online.

After a whole 2 minutes of googling I figure out all I need to run are:

sudo apt-get update

sudo apt-get install ssh-server

Done. Now fire up putty and try to connect or “ssh -p 22 localhost”.