yogsloth: Step 1) Go to your local record store
Step 2) Browse through the music for sale. Find releases that catch your eye and peak your interest.
Step 3) Ask questions to other customers and to the people on staff. See what's available in the listening stations.
Step 4) Actually pay real money for the product you wish to consume, ensuring that music will still exist in the future
Step 5) Listen to the music you purchased. Fall in love with it. Have it move your soul and change your life. Listen often.
That's all well and good... but we don't have music stores over here anymore. Ok, there's a HMV in my local town but it's not really worth bothering with. And last time I checked they certainly don't have listening stations any more.
And if you started talking to random people about stuff in this country you're likely to get stabbed...
I always struggle to find new music that I really like (or even old music I like and hadn't heard before), the radio feature others have mentioned is alright but I find it tends to play mostly the same well known kind of stuff rather then really giving you hidden gems or things you may not have heard / heard of before...
I tend to like looking for the bands that the bands I like like (that sentence looks wrong but I think it makes sense), the people who influenced them etc.
It doesn't always work, but I've found quite a few bands I like that way.