There are many guides that describe different aspects of setting up a VPS but I couldn't find one which brought it all together to create a ColdFusion host. So in the great internet tradition of building on others work, here's my contribution. The focus here is to provide a specific recommendation for each step, link to a definitive guide in setting it up, and also briefly mention the alternatives.

The initial setup

1. Choose a VPS host
Features to consider when choosing a host are bandwidth, RAM, processor share, the servers physical location, reliability and reputation. I went with Linode selecting  a VPS in Freemont, CA, as it's closest to the pipe connecting to Australian, while still servicing the U.S. market well. Here's the getting started guide for setting up a Linode VPS and choosing the operating system, very simple.

Alternatives: Slicehost is very popular and has a great community, but currently the value for money on the plans isn't so competitive. Rackspace Cloud offers better server resources but you are charged by the hour that it's powered on and you purchase the bandwidth separately, making it a good option if you're starting out with a low bandwidth site or require backup or test servers.

2. DNS Setup
First go to the the site where you registered your domains and update the nameservers for the domain to point to your VPS provider. Then in your VPS control panel define the DNS records for the domain. Here are the instructions for Linode, if you are using a different host check in their support section.

Note: From here on the title of each step links to the clearest setup guide I could find.

3. Operating System : CentOS
These instructions describe the initial setup and securing of your VPS. They come from Slicehost but they'll serve you even if you are using a VPS from a different host.

Alternatives: You can't really go to wrong with most of the established Linux OS's. Stick with what you know and make sure there's support for it: The Slicehost Articles site is an excellent resource.

Installing the services

4. Web Server: Apache
An easy choice, ignore the PHP section in the tutorial if you don't require it.

Alternatives: Your Java Application Server (such as Tomcat or Resin) could function as the webserver. Or there are lightweight, high performance web servers which offer excellent performance like nginx and lighttpd  but if you are setting up your first VPS then going for one of these is probably overkill.

5. Database Server: MySQL

Alternatives: Postgres is actually my preferred option but there are a couple of applications I'm using which don't support it, so I've gone with the safe bet.

6. Java
Required by which ever ColdFusion engine you use, so not a lot more to say here.

7. The ColdFusion Server: Tomcat & Railo
Railo is a high performance open source ColdFusion engine which is seeing very good community support.

Alternatives:  Open Blue Dragon is an alternative open source ColdFusion engine and, of course, there's the commercial option of Adobe's ColdFusion.

8. Mail Server: Google Apps
Why give yourself the extra headache of managing a mail server and spam filters with all the risks involved? For me there was no question: using the Google Apps is by far the simplest option. Note that when setting up the Google SMTP server in the ColdFusion Administrator you should set the port to 587 and select the TLS option but not the SSL option.

Alternatives: Postfix

Keeping an eye on it

9. Statistics: AWStats & Google Analytics
AWStats is a Perl script which analyses the webserver logs directly, giving you real time statistics on all activity. It's also useful for being able to highlight missing and error pages and hack attempts. Google Analytics provides more in depth analysis on what it collects but will miss those who have JavaScript disabled.

10. Uptime Monitoring: Pingdom
Being alerted when your server goes down is essential to keep your clients happy. Pingdom provides a nice clean interface, charting and sms alerts.

11. Backups : rsnapshot
This a remote filesystem snapshot utility, based on rsync and I've got this setup on a separate server to take scheduled backups from the VPS. It's not too complicated to setup and very flexible, supporting backups of MYSQL databases, you could even run it from a server at home if needed and when you need to restore some data you'll be very happy to have it setup.

12. Keep It Updated
It's important to keep your system and the installed packages secure and updated. On Centos this means running "sudo yum update" when there's an update that needs to be applied.

You'll also need to individually update other packages you've installed manually. Railo makes this process very easy: simply login to the server administrator and select 'Update' which is under the 'Services' menu.

Generally it's a good idea to subscribe to an RSS feed from whoever provides the software you are using so you can be alerted if there's a security patch which needs to be applied.

Need More Help?

There's loads of great resources out there: the first step should be a web search. If you are seeing a specific error message then search for the text of the message along with the application name.

Then there are the blogs, forums and IRC channels for the service you are having trouble with. Twitter can also be very useful here too, tag the topic of your question with a # and someone will pick it up, e.g. #railo or #centos. The trick is figuring out a concise and accurate description of the problem; once you've done that you're half way there.

Finally, there are wiki-like question and answer websites which can be very helpful. For server setup issues Server Fault is emerging as a great resource. Its sister site Stack OverFlow does the same thing for programming problems.

Good luck!