Spotify is finally available for Linux users (native) but unfortunately only for Premium accounts because:
As we haven’t found a reliable way to display ads yet, this version is only available to Spotify Premium subscribers.
This makes the Spotify for Linux rather useless since there are already a few unofficial Spotify Linux clients out there which also work only for premium users.
But this is a preview release (which doesn't play local music, among other things) so we can expect a fully featured Spotify client for any type of accounts (including free) soon.
The Linux Spotify client comes in a repository available for Debian Squeeze / Ubuntu 10.04.