Users would upload their copies of the music and spotify would replay them. This was obvious to early users, even if they were only consumers, because of the pirate-shout-out-overlays that were in a lot of the poorer quality releases.
Another interesting note, in the early days of spotify, the app would saturate your upload bandwidth while using it. Given their close ties to utorrent, I always assumed that's how they were affording the bandwidth as well.
Pretty brilliant way to bootstrap I guess; they didn't have to pay for bandwidth or content until they already had contracts in place
