There are a few likely ways they got this information:
- Through a virus on your computer
- Through a phishing campaign, where you clicked on something because you thought it was official
- Through a social engineering attack; in other words, they got it from you personally because you told someone
- Through an attack on some other website, likely where you used the email address and the same password
- Through sniffing your wireless internet traffic if it has no password and goes over an unencrypted channel (http versus https, make sure your email is accessed through https if you use a browser; eg, gmail.)
#3 is pretty unlikely, though do note that if you share the email account password with anyone, they could also have fallen to the same thing.
What to do now:
- If you're using gmail for example, you can make sure to log everyone else out of your account who might be using it
- Change the password ASAP, to a password you never use anywhere else. A simple strategy is to use a phrase, for example, "ILikePuppies" or something. Another is to use a randomly generated string, "A0$gub88zi". You can imagine which is easier to remember.
- Scan your computer for viruses using free anti-virus software. Microsoft provides decent free software on windows 8/8.1, included in the OS by default. Viruses, trojans, keyloggers, malware of all sorts can grab your key inputs or internet traffic.
- Speaking of which, ensure that your wifi, if you are using it, is password-protected.
- If any are found, delete it... and maybe change the password again.
- Change your bank passwords as well, again, make sure they are unique and strong. Otherwise, they may use your email + password to access bank accounts.
Shit happens. You'll be fine after you do this, unless someone has personally picked you out to mess with (chances of that are approximately zero.)