My solution is to develop an algorithm for all my passwords that is pretty quick and simple to memorize but allows me to "generate" a unique password for each service that I use.
Although I seriously doubt anyone could figure out my algorithm by learning one of my passwords, I'll admit that if they were to gather 3 or more then they'll probably be able to figure out my system. But since I never write down or record any passwords whatsoever (all I need to remember is my algorithm), someone would have to steal my credentials from multilple sources and also be able to know which credentials from one service match a user from another, etc.