Ask HN: How does Spotify do it?

I looked at Spotify today and It confuses me how they can allow anyone to play any song, anytime? What about licensing to the record companies?

What am I missing?

Are they paying licensing to the record companies or do they not have to since it is just streaming, not illegally copying the music like Lime or Napster?