Firewall Settings
Have you checked the firewall settings? You need to set TCP port 5800/5801 open (depending on set up - you could use an ssh tunnel, but that is more complicated). Note that various root server providers have firewalls set up between you and the root server, so you may have to go into a web interface to open up the relevant port. For example with Amazon EC2 you would have to run ec2-authorize to let traffic through, as well as opening up the port on the server itself.
VNC server
You then need to start the VNC server, and only then can the client connect to the server. We use xtightvnc as it is meant to be good at compression. An initial step is to set up your VNC password - the password you will have to type into your VNC client to join the VNC session. To do this you use vncpasswd
(man page) on the console on the server.
So to start the server on display 1 (so port 5801) you need to run something like this command on a console on the server, as the user you want to be:
tightvncserver -geometry 1024x768 -depth 15 :1
See the man page for more details on the various options. Then you can connect with your client, to port 5801.
Web options
As well as the desktop client, there are also a couple of options for running VNC in the browser. For older browsers there is a VNC client java applet that will run in the browser. For more modern browsers (with the HTML 5 Canvas element) you can run Guacamole - a java service that lets you have a VNC session run directly in your browser. (Strictly it is running its own special protocol, and the guacamole service running on your server translates that into VNC. So for guacamole to work you also need port 4822 to be open.)
Automating it all
I know by this point I'm getting away from directly answering the question a bit, but I did some fun stuff to automate setting up, joining and tearing down VNC sessions using fabric (a python deployment library) I'd like to share. Read the link to learn more.