Although I'm sure these exact commands work fine for other versions, this is the specific set of commands that I use to install the Ubuntu Gnome desktop and VNC on 12.04.
First, run updates.
apt-get update && apt-get -y upgrade
Then, install the desktop, VNC, and nano. This might take a few minutes
apt-get install ubuntu-desktop vnc4server nano
Next, run vncserver for a moment to create some required files.
vncserver
(Set your password when asked)
Go ahead and kill the VNC server.
vncserver -kill :1
Let's edit the startup file.
nano ~/.vnc/xstartup
Add the following line to the bottom:
gnome-session &
Use Control+O to save, hit enter. Control+X to exit.
Start vncserver again.
vncserver
VNC into your VPS using the IP address and port 5901.