http://www.socialblogr.com/2010/05/how-to-install-empathy-themes.html

Pues sin saber cuáles son esas opciones que encuentras en Google difícil lo tenemos...
En Ubuntu basta con descomprimir el tema descargado en /usr/share/adium/message-styles/ (ahora no tengo forma de probarlo en Debian, pero puedes probar a ver si funciona).

Bueno blackhalo, esa es la opción que encuentro googleando pero en debian no existe esa carpeta.

Caliban instalar el deb da error, me dice que empathy-chat-theme depende de ubuntu-standard, que se puede hacer en ese caso.

Como ya he dicho, ahora mismo no tengo forma de corroborar en Debian lo que te digo pero... ¿has probado a crear tú la carpeta?

Otra opción es descargar los temas en ~/.local/share/adium/message-styles/*.AdiumMessageStyle (todos los temas tienen que tener ese nombre)

Se hace tal cual explica Blackhalo. Probado y funcionando en Debian.
Saludos

Claro que creé las carpetas pero no funcionó, leyendo en live.gnome.org que su puede tener el soporte solo si está construido con soporte para webkitgtk+, pero Ubuntu no tiene instalado webkitgtk+ o al menos eso creo, busqué en los repositorios y no encuentro ese paquete, en la página oficial de webkitgtk+ se dice de una forma de instalarlo en Debian pero no estoy muy seguro si esa es a la Debian way, alguna sugerencia?.

OK, tienes razón blackhalo, cometí un error al crear las carpetas pues las creé creé ~/.local/adium/message-styles, ya corregí la ubicación de ellas y todo funciona perfectamente bien .