I never listened to the radio to begin with. Even before the internet, and not listening to the radio, I still bought new music regularly. I generally depended on word of mouth and hearing friend's albums to decide what new music I want to buy. Sometimes I would hear a tune on a movie soundtrack or something and get into an artist that way.

Nowadays, you can find music similar to your tastes by browsing your favorite artists at allmusic.com or amazon.com. The Amazon "other people who bought this album also bought X" feature is rather good, actually. And you can go through and rate albums you own and have it make recommendations. Agreed, the recommendations are not always perfect, but that's why the offer audio samples.

For instant gratification, many record stores now offer kiosks where you can sample large numbers of albums right there in the store.