1- Para instalarlo edita el sources.list

$ sudo vim /etc/apt/sources.list

2- Agrega la siguientes líneas (una sola línea):

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

3- Desinstala las versiones anteriores de KDE 4.0 que tengas instaladas.

$ sudo aptitude remove kdelibs5 kde4base-data kde4libs-data

4- Actualizamos el source.list y instalamos KDE 4:

$ sudo aptitude update
$ sudo aptitude install kde4-core

Vuelve a iniciar una sesión escogiendo KDE y listo