Generally, curiosity kills the cat for me. I'll find a band I enjoy usually through other bands. (For instance, one band thanks another band in the liner notes for an album, I check out said band who was thanked, etc.) Plus, it seems like a lot of bands I listen share some members over time, so the lines begin to blur.
I'll also search by record labels; I've found that this is generally a tedious thing sometimes, as labels have both brilliant and awful artists. But it's a good way to find out what record labels are really about.
I'm also a subscriber to the Zune Pass, so I'm always getting recommended new stuff to listen to. Last.fm is pretty rockin' too.