This post is over 3 years old, so please keep in mind that some of its content might not be relevant anymore.
My favourite NX server is Freenx.
FreeNX is a GPL implementation of the NX server/client that allows you to graphically access your machine over the Internet.
FreeNX runs natively on SSH, it’s open source and, above all, fast.
So, first of all you need to add the free-nx repository:
sudo add-apt-repository ppa:freenx-team
and then update and install freenx:
sudo apt-get update
sudo apt-get install freenx
The client I use instead, is from NoMachine.
The Linux version can be download from here.
If you use a different Ubuntu version you can follow the Freenx documentation.
Enjoy.