Here is what I do:
I disconnect my internet, reboot, and use vanitygen (
https://bitcointalk.org/index.php?topic=25804.0) to create a public/private key pair.
I
carefully copy the private key in pencil onto two pieces of paper, and then
make sure that the papers match. I then destroy any files made by vanitygen.
I fold the papers with the private key on the inside, and write the public key on the outside.
I put each one in a safe place, in different cities.
There are more colourful ways to make paper wallets, but I like how low-tech this way feels.
Sometimes, I send a small test transaction to the paper wallet's public address and then import the private key into a fresh bitcoin-qt wallet to make sure I copied everything down correctly. This also gives me an address entry in my main wallet that I can copy when I send my real savings. Then, I destroy the wallet file bitcoin-qt created for the paper wallet.