The first obvious thing to try, of course, was directly forwarding X. That was just too slow. Next was VNC. I tried tightvnc, realvnc, vino, etc. The only usable setting I found was 8-bit colour and using Hextile encodig. However, it wasn't very enjoyable.
Then I discovered FreeNX. It's fast, secure, stable, user-friendly, and very pleasing to the eye. Here's how to set it up on Ubuntu 8.04.
Server Setup:
------------------------
Step1: Update your current installation
prompt%> sudo apt-get update && sudo apt-get upgrade
Step2: Add the repository for th NX packages & get them
prompt%> sudo vi /etc/apt/sources.list
Add the following lines:
deb http://ppa.launchpad.net/marceloshima/ubuntu hardy main
deb-src http://ppa.launchpad.net/marceloshima/ubuntu hardy main
Install:
prompt%> sudo apt-get install expect openssh-server nxlibs nxagent nxproxy freenx-server
Step3: Add your account
prompt%> sudo /usr/bin/nxserver --useradd < username > --system --administrator
Step4: Startup the NX server
prompt%> sudo /usr/bin/nxserver --start or --stop or --restart
Client setup
------------------------
Step1: Download the client
prompt%> wget http://64.34.161.181/download/3.2.0/Linux/nxclient_3.2.0-9_i386.deb
Step2: Install it
prompt%> sudo dpkg -i nxclient_3.2.0-9_i386.deb
If you are using a windows machine, you can get a client from here:
http://64.34.161.181/download/3.2.0/Windows/nxclient-3.2.0-10.exe
Step3: Run the client
prompt%> /usr/NX/bin/nxclient
Enjoy!

Update 2008-06-26:
For AMD64, its just about the same:
1) Get SSHD:
prmpt%> sudo apt-get install openssh-server
2) Get 3 packages from here.
3) Install:
prompt%> sudo dpkg -i nxclient_3.2.0-9_x86_64.deb
prompt%> sudo dpkg -i nxnode_3.2.0-11_x86_64.deb
prompt%> sudo dpkg -i nxserver_3.2.0-13_x86_64.deb
4) Start server
/usr/NX/bin/nxserver --status|--start|--stop|--restart
Enjoy!
References:
http://www.drtek.ca/freenx-server-ubuntu-hardy

