I personally use KeePass, which isn't cloud-based, but I drop the database file into my Dropbox. I also have a copy of KeePass portable and my database on a disk-on-key which I keep on my keychain. This isn't usually up-to-date, but it does have the most important stuff in there.
LastPass is fantastic (http://lastpass.com/) for website passwords, but isn't too great for non-websites. It's very similar to 1Password, but cross-platform. It can be used to manage non-web passwords, but it's kind of a manual process using their secure notes.
I use Bruce Schneier's advice and keep them on a piece of paper in my wallet. Always safe and available. Of course, I only have a few dozen, not the hundreds some people claim they have to manage.
I store the data file on dropbox, so it is replicated across different machines I use. Each machine has the PasswordSafe program (binary) installed on it.