This is a subpost of the larger post Updated Comprehensive VPS Setup Documentation.
I like Digital Ocean (Referral Link) for my VPS host.
The first step in creating a new VPS is to select a Linux distribution. I always use the most current version of Debian. At the time of this post, that is version 8.3 x64.
Decide on an FQDN and use it as the hostname and hit deploy!
It should take about a minute and then you will receive an email with the temporary root password. Use putty to log in, and you will be prompted to change it.
Make sure to choose a root passsword with a high level of entropy.