Para uma solução baseada em NX, sugiro usar o X2go. Não é compatível com o cliente Nomachines ou OpenNX, mas é muito melhor integrado com coisas como o PulseAudio. Isso significa que você pode ter áudio bidirecional com a área de trabalho remota, por exemplo. Eles têm vários clientes legais, incluindo um plugin do Firefox. Como outras soluções baseadas em NX, ele é executado em ssh.
Para fazer isso, basta instalar o pacote ubuntu-desktop e instalar o x2go. Se você ainda não tem o openssh-server instalado, você precisará dele também, mas se for um servidor headless, eu acho que você já tem isso. Você não diz qual versão do Ubuntu você está usando, mas se for 11.10, provavelmente você vai querer testar o Unity 2D. O cliente X2go pode precisar ser configurado para isso. É provável que você também queira desabilitar o LightDM ou o GDM, já que não serviria em nenhum propósito em um servidor sem cabeçalho. A maneira mais fácil de fazer isso pode ser simplesmente desinstalá-lo.
Existem também outros ambientes de trabalho que você pode querer experimentar. O LXDE é muito rápido e bastante adequado para um servidor de terminal. Então, se Xfce.