Spotify rolls out a preview version of "Spotify for Linux," that shares most of the same features as Windows and Mac OS X desktop applications, and is currently available for Debian Squeeze/Ubuntu 10.04 package.
"Unfortunately, there're issues regarding decoding of local music on the Linux platform so we haven't included support for local files in this version. As a preview release this version is still unsupported, but we're running it ourselves and will try to make sure it keeps pace with its Mac and Windows siblings. As we haven't found a reliable way to display ads yet, this version is only available to Spotify Premium subscribers," stated Spotify.
More Info: Spotify for Linux