Está incluido en los repositorios de Hardy con lo cual para instalarlo basta con ingresar a una consola y escribir:
sudo apt-get install rdesktop grdesktop
Lo último es un front end gráfico para utilizarlo desde Gnome, Aplicaciones > Internet > Remote Desktop Client.
También se puede usar desde la consola:
rdesktop -4 -u {nombre usuario} -g 800×600 -T Remotedesktop-Client:{nombre equipo remoto} {nombre equipo remoto}