On client:-
Generate an ssh key as the required user.

ssh-keygen -t rsa

All defaults. Leave password blank.
Still on Client:-

cd
cat .ssh/id_rsa.pub | ssh serveraddress 'cat >> .ssh/authorized_keys'

Done! For putty on Windows into a Linux box the idea is the same although you need to use the -i flag of ssh-keygen to: 'Convert RFC 4716 to OpenSSH key file.' Use puttygen (see below) to create a key-pair on Windows, copy the key to Linux machine and then:-

ssh-keygen -i -f key.pub >> ~/.ssh/authorized_keys

Actually it looks like puttygen can do the whole job by itself now (it has an ssh_keygen of it's own). One thing to note the permissions for .ssh directory:-

chmod 700 .ssh
cd .ssh
chmod 400 authorized_keys

Make sure you are using the correct port if you're in a VM behind another server!