Hay que descomentar en el fichero /etc/kde3/kdm/kdmrc la línea que pone:

UseTheme=true

Luego, en la que pone Theme=@@@ToBeReplacedByDesktopBase@@@

sustituir por el tema que queramos poner de la carpeta /usr/share/apps/kdm/themes/, por ejemplo:

Theme=/usr/share/apps/kdm/themes/daemonic-smegma_1.0

Reiniciamos kdm con /etc/init.d/kdm restart.