Billy Talent -- Heard of them from one of the 'Burnout' games for the PS2. Don't ask which one; I own them all for the PS2, and I'm not going through them all just to find them. I own all their albums now, and they are probably one of my all-time favorite bands.
King Diamond -- I was really into heavy metal when I was growing up, took a chance blindly ordering the 'Conspiracy' tape through the mail, and I still listen to him to this day. The man is a vocal and songwriting genius.
Muse, Air, Emily Loizeau, Modest Mouse, Kaiser Chiefs -- Blame XM Radio.
Volbeat -- A friend who lives in Sacramento burned us a CD to listen to for the drive back home.
Lillian Axe -- My friend bought their tape thinking it was a female singer/group. That was funny. Even though wasn't what she thought, still not bad.
Nuno, Ny Loose -- When I was a teenager, the record shop I used to visit whenever I could would put out free sampler tapes of the newest rock/indie music to hit the scene. Nuno's song on there was 'Crave' and Ny Loose's was 'Rip Me Up'.
Yes, I am old. When I say 'record shop' they really DID sell records. If I couldn't buy it locally, I'd order music through the mail (often without ever hearing the band first) I got pretty good at researching bands through metal magazines before I bought my music. Through reviews and interveiws, I generally had a good idea of what to expect.