$ sudo apt-get install vnc4server
# the following will require a password setup
$ vnc4server -geometry 1024x768 -depth 24
# the following will output something like New 'Hostname:1 (user)' desktop is Tethys:1
$ vnc4server

# Now all that is left is to add to ~/.vnc/xstartup, the following
# The rest is the same
# add the following which creates a gnome-session on startup
gnome-session

http://www.debianhelp.co.uk/vnc.htm

This is based upon a debian guide, it seems to work well for ubuntu as well, all these steps can be performed via remote ssh (no need to access the machine).

setting up vnc debian way

server, ubuntu

Bash