Some Internet companies that were vulnerable to the bug have already updated their servers with a security patch to fix the issue. This means you'll need to go in and change your passwords immediately for these sites. Even that is no guarantee that your information wasn't already compromised, but there's also no indication that hackers knew about the exploit before this week. The companies that are advising customers to change their passwords are doing so as a precautionary measure.
Also, if you reused the same password on multiple sites, and one of those sites was vulnerable, you'll need to change the password everywhere. It's not a good idea to use the same password across multiple sites, anyway.
Go buy 1password already.
Heartbleed should bleed X.509 to death:
4 companies controlling 90.6% of the internet's secrets. This is fucking insane. Do you have any reason to trust this lot with anything, no less the security of 90.6% of all your 'secure' internet traffic? Do you honestly believe that the NSA/GCHQ didn't see this and say "Well that could be a lot worse"?
What we have done here is fitted our doors with some mega heavy duty locks, and given the master keys to a loyal little dog. Sure, he barks at you with a smile, but can you ever be sure he won't be distracted by an appealing steak from your worst enemy? Of course not, he's a fucking dog. We've seen two-faced dogs before - one was called RSA. They just loved that NSA steak.
At this point, the probability is close to one that every target has had its private keys extracted by multiple intelligence agencies. The real question is whether or not someone deliberately inserted this bug into OpenSSL, and has had two years of unfettered access to everything. My guess is accident, but I have no proof.
I'm hearing that the CAs are completely clogged, trying to reissue so many new certificates. And I'm not sure we have anything close to the infrastructure necessary to revoke half a million certificates.
Possible evidence that Heartbleed was exploited last year.
Also I'd like to point out again that nearly every security bug you've experienced in your entire life was Dennis Ritchie's fault, for building the single most catastrophic design bug in the history of computing into the C language: the null-terminated string. Thanks, Dennis. Your gift keeps on giving.