Heartbleed is a bug in OpenSSL that could potentially expose your information to people that would do very bad things with your information. Servers are currently being patched, but it can’t hurt to change those passwords too. Mashable has a list of websites and services that have been hit and advice on what you should do.
It might also be a good idea to see Mozilla’s advice on how to choose a strong password that you’ll actually remember.