** Be careful and make sure you have console access to the box because if you don't do it right, you won't be able to ssh in again until you fix it from the console.
The process is much easier than you think. Load the public / private key pair you generated in puttygen again. In puttygen, you'll notice a window in the middle of the screen which says: "Public key for pasting into Open SSH authorized_keys file:".
highlight the entire contents of the box and press control-c to copy it.
SSH into your linux box and paste it into the "/home/username/.ssh/authorized_keys" file. I prefer to use nano and just right click to paste it in. Make sure it all stays on one line.
Modify your /etc/sshd_config file as needed and restart your sshd service: "service ssh restart"
If you need a sample sshd_config file, let me know and I can post mine.
I've done this on Ubuntu 8.04, 10.04 and 12.04 LTS server and it works slick.