En Debian Amarok viene por defecto en los paquetes, así que solo hay que instalarlo (como root):

apt-get install amarok

Si el paquete no esta disponible, podes descargarlo acá.

Primero tenes que acceder a los repositorios:

sudo gedit /etc/apt/sources.list

Y pega esta linea al final del archivo:

deb http://ppa.launchpad.net/kubuntu-members-kde4/ubuntu jaunty main

Ahora instala Amarok:

sudo apt-get install amarok

Y ya tendrás Amarok listo para usar.

En Fedora el Amarok ya viene en los paquetes.
Para instalarlo ejecuta los siguientes comandos:

sudo yum install amarok

sudo yum groupinstall sound-and-video

Para instalar amarok en Gentoo simplemente ejecuta:

emerge -av amarok