Now, I've decided that there is no real effective solution other than randomly generated passwords unique to each site.
I also turned on 2-factor auth for Gmail a couple months ago - their SMS system is really effective.
I do have to credit Google for being extremely awesome when it comes to security... They noticed a few "your password has been changed" emails incoming to my inbox yesterday and immediately put a security flag on my account, requiring me to re-auth with 2-factor and change my password. Google is really proactive when it comes to security. The fact that they can recognize a high number of password change emails arriving as an indicator of possibly account hijacking is just amazing.
I think LastPass is probably as good of a solution as any. They only store your encrypted password database in the cloud. With a strong enough master password and optional 2-factor authentication with Yubikey, it seems quite secure.