Spotify is an audio application that allows users to stream audio from Spotify’s servers. But, unlike many other services (i.e. Pandora), it only plays the songs you tell it to. The free version is supported by ads, however a low monthly fee will remove the ads.
Spotify has made a “preview” version for Linux. Currently, Spotify will run under Wine (or under Wine with PlayOnLinux assistance) without much problem, but native versions are always better.
The Linux Preview is available for Debian/Ubuntu by adding a package repository. I gave it a spin, it seems to be fairly stable and works just fine. Occasionally, when it stops to buffer (I have slow internet), it won’t start playing again by itself. Still, Spotify for Linux is definitely an application I will be keeping around.
You can learn how to install Spotify for Linux here:
http://www.spotify.com/us/download/previews/