Leave it to Randall Munroe of xkcd fame to put this massive security bug in plain (drawn) terms. The technical details behind the encryption vulnerablility might be confusing even for those of us who know what SSL means, but as this comic points out, basically it means we're screwed.
Or, more precisely, the bug allowed at least for the last two years any user to query a web server (for sites like Yahoo and Google) and see the requests from other users. Stuff like passwords, credit card information, and other sensitive details.
You should change your passwords--but wait until the sites have fixed the vulnerabilities fully (and that should include reissuing security certificates. The best source I can find for that right now is LastPass's Heartbleed security checker).
Here's the xkcd explanation: