The Heartbleed OpenSSL vulnerability (CVE-2014-0160) may affect 2/3rds of the servers on the Internet. It allows 64K of user information to be collected by unknown unauthorized individuals, and it means that some percentage of your usernames and passwords have been compromisable for about two years.
This vulnerability has several major classes of player on the field:
1.) The operating system vendors - It is surprising that the operating system vendors didn't notice this vulnerability. They vet applications for security before they are approved for use in the operating system.
2.) The server administrators - It is not ok that they collectively didn't find this problem for 2 years, because there has been an open gate to private materials and data for all of that time on millions of servers they are working with every day. They have been working on upgrading their OpenSSL applications and replacing their security keys, since this issue surfaced. There may be a few servers that don't get upgraded to the safe version of OpenSSL, but that should be a relatively small number.
3.) The domain owners/managers - all domains that have https secure html sites have got to replace their SSL keys. This is not because the keys were damaged, but because they might have been leaked to the Internet at large. Keys are often updated annually, so this is not as huge an unexpected expense you might at first assume. Some of the server administrators only have a single domain on their servers, so these 2 roles would be the same.
Here's where you come in..
4.) You are the one with logins at Facebook.com, Google.com, Yahoo.com and many other places. The first thing you might want to consider is you have been trusting anonymous strangers to guard your safety since before you were born. Entry into the Internet world didn't change that. In a funny way, you must be pretty important for all those anonymous strangers to be looking after you for all these years. You are being given a chance to review your own security hygiene. You don't want smelly security, do you?
Physical Security Hygiene
As a person who lives in a building, you practice physical security hygiene most of the time. You have locks for the doors and windows, chains for the doors, alarm systems, fences, and gates. You may lock your car doors and take the keys with you when you drive someplace. You would consider somebody who didn't follow all these patterns to be naive or stupid. You probably maintain very good physical security hygiene, and if you discover a place where that hygiene is not up to par, you probably fix it as quickly as you are able.
Digital Security Hygiene
Your digital security hygiene may be just as immaculate. You may have different passwords for each of the places you log in to. You may change those passwords at least annually, and you may protect your passwords from others (no sharing). Lots of us are not so careful about our digital hygiene.
The reason to have good digital security hygiene is that your information, when spread to anonymous strangers can cause trouble. The personal data could be used to steal your identity. Your credit cards could be used to buy things in your name that you do not want. Your computer could be infected and owned by somebody who will use it as a base for attacking others. Even if you have nothing in the bank account, and your credit cards are maxed already and you have nothing but pictures from your summer vacation on your computer, sloppy digital security hygiene can have a negative effect upon you and others.
How do you remember all those passwords with at least 8 characters, a number, a secret sign, a capital letter, and all the other complex stuff that we are told the password must contain? How about using your browser to remember the passwords? This is itself a bit of a physical security risk, but if your computer is physically secure and you have a good password to log in to the computer, it is far less dangerous than writing them all on a notebook. A better solution might be using a program like KeePass, which keeps all your passwords encrypted and protected by a master password. You can keep very long complex passwords there, and not usually have to worry about decrypting your password hash if it is stolen from a web site.
For sites that you may have to visit occasionally from other computers, you might need a password you can remember easily. One method is to think of song lyrics you always remember, for instance, "There's a lady who knows all that glitters is gold, and she's buying a stairway to Heaven." Take the first letters and the punctuation and make that a password. "Talwkatgig,as'bastH." would be easy to remember, is not a dictionary word (except, possibly, in Klingon), and is 19 characters long. Don't use the same password on all of your special sites, of course.
Finally - Don't Panic!
This vulnerability has been available for 2 years, and there is not yet much evidence that your passwords have been used against you. You don't need to wait until somebody does finally decrypt your password, since you really should be changing your passwords on an annual basis anyway. Realize you have been lucky. Change your passwords, and get on with your life.