Here's my advice on password security based on the collected opinions of others:
1. Write them down and keep them in your wallet because you are good at securing your wallet. (ref)
2. Use different passwords on every web site because if you don't one site hacked = all your accounts hacked. (ref)
3. Use passwords of at least 12 characters. (ref)
4. Use mixed-case, numbers and special characters. (ref)
Research says you need 80-bits of entropy in your password so it needs to be long, chosen from a wide range of characters and chosen randomly. My scheme gives me 104 bits of entropy.
My passwords are generated using a little program I wrote that chooses random characters (using a cryptographically secure random number generator) and then printing them out on a tabula recta. If you were to steal my wallet you would find a sheet of paper that looks like this in it (I have a second copy of that sheet left with a friend in an envelope):
I use that sheet as follows. If I'm logging into Amazon I'll find the intersection of column M and column A (the second and third letters of Amazon) and then read off diagonally 16 characters. That would be my Amazon password (in this case, TZ'k}T'p39m-Y>4d); when I hit the edge of the paper I just follow the edge).
The security of this system rests on the randomness of the generated characters and the piece of paper.
PS Yes, it's a total pain to use long, random, different passwords.
PPS If it's not obvious to people you can add a second factor to this (something only you know) in the form of the algorithm for picking the password from the sheet. For example, instead of using the second and third characters from the site name you could pick any combination. And you could change the letters as well (e.g. for Amazon you could use the last two letters moved on one place in the alphabet; you'd have PO as the key). Also you don't have to read diagonally but could use any scheme that works for you (e.g. a spiral pattern, read vertically, read characters at offsets from the start based on the Fibonacci sequence, etc.).