A maneira mais simples no Ubuntu seria rodar esses dois comandos
sudo apt-get install libasound2-plugins libasound2-python libsox-fmt-all
sudo apt-get install sox
Se você está em algum outro Linux, como o CentOS ou precisa de suporte para Vorbis e Ogg, você terá que compilar a partir do código-fonte, seguindo seguindo este Guia