If you want to use Spotify on Linux, you’ll have to execute it in wine, which works great most of the times. There are even easy instructions on the Spotify’s website how to configure it for best results.
The website has also instructions how to install a spotify:// URL handler, but these are bit ugly and only work for Firefox and Epiphany. There is a nicer way of doing this in GNOME, and this is by using gconftool and installing them in gconf, this way all applications will know how to handle a given URL. In a terminal window, just type:
gconftool-2 --set --type=string /desktop/gnome/url-handlers/spotify/command 'wine "C:\Program Files\Spotify\spotify.exe" /uri "%s"' gconftool-2 --set --type=boolean /desktop/gnome/url-handlers/spotify/enabled true gconftool-2 --set --type=boolean /desktop/gnome/url-handlers/spotify/need-terminal false