First of all, I discovered that on Linux Mint 12, the firewall is turned on by default which prevented me from loging on to 'leia' with ssh. So, make sure your firewall is letting traffic through on port 22.
Now, generate keys as usual on your local host and enter a password for them:
vader$> ssh-keygen -t rsa
Install the public key on the host you want to connect to:
In my case, it looks like this:
vader$> ssh-copy-id -i ~/.ssh/id_rsa.pub peter@leia
Now, it is time to load your key into memory. This is done with the program ssh-add, but first you have to start an instance of ssh-agent.
vader$> ssh-agent bash
The ssh-add command will automatically load ~/.ssh/id_rsa into the agent and ask you for the password you've set. From now on I don't have to enter a password when logging in to leia, as long as I stay in the ssh-agent shell.