To compete with the likes of Pandora, Spotify has now announced their free service will also be available on mobile

http://news.cnet.com/8301-1035_3-57615239-94/spotifys-mobile-app-finally-goes-free/

The free service is available with ads (like on the desktop), but with some restrictions:

"Users can access their playlists and music albums, but they have to scroll through their lists randomly using a "Shuffle Play" button. Users can't pick the exact song they want to play right away, and will have to shuffle through their playlists."