They pay licensing deals with music labels, and always have.
They were following in the footsteps of other Internet radio companies like Pandora, who worked out many of the kinks regarding licensing the music played in a randomized style, and watched for minefields hit by other media sharing groups like the original Napster.
By the time Spotify came out in 2006, most of the major legal issued had been identified. The initial founders pushed in a bunch of money, probably a few million USD equivalent, and by launching in nations more friendly to streamed music to develop their company, they had developed a following over the course of about five years before opening up in the US where lawsuits were the highest risk.