While Spotify does not directly support a client for Linux they provide a preview client that was released for the old stable Debian (Squeeze). Unfortunately this is incompatible with the new stable version, Wheezy, due to a dependency problem. However, there’s a quick solution that let’s you run the client on Wheezy, too.
The problem is that on Wheezy the libssl library switched from 0.9.8 to version 1.0.0. The Spotify client however is built against the older version missing on a recent system. Until they release a new client to correct this issue you can easily fix this by installing the old libssl in parallel to the new one. Just obtain the correct .deb file for your architecture from http://packages.debian.org/squeeze/libssl0.9.8 and install it by running the following command:
root # dpkg -i <debfile>
Afterwards the Spotify client should install just fine.