I think it's vital to have a different username, email, and randomly generated password for every site.
That makes it impossible to remember, so you have to write it down somehow.
Paper isn't the worst option...
I'm wary of web-based password managers, e.g. Lastpass, because it's a big juicy target.
I use KeyPass portable, it's basically just a handy encrypted notepad, and I have a strong master password that isn't used anywhere else.
If you're going to use KeyPass portable you need to back it up somewhere, whether that's USB, cloud storage, etc, is your call.
The backup becomes the most vulnerable point, so secure it the best you can.