sudo apt-add-repository -y "deb http://repository.spotify.com stable non-free" &&
sudo apt-key adv --keyserver keyserver.ubuntu.com --recv-keys D2C19886 &&
sudo apt-get update -qq &&
sudo apt-get install spotify-client

Fuente: http://howtoubuntu.org/how-to-install-spotify-in-ubuntu

Tambien funciona para Elementary OS