How did these amazing artists that no one really listened to get their CD in the store?

I think there is a lot of hindsight bias here. The internet made shelf space unlimited, and artist that used to toil away in absolute obscurity now have a shot. I don't think we're talking about those who would have had a CD on the local store shelves, we're talking about those playing at random bars in their town.