http://vagrantup.com is a good way to get started on your local machine (without paying a VPS provider). You can install a minimal operating system and build up your stack from there. Because it is completely free, you can recreate your server and really experiment with different operating systems until you feel comfortable to go live.

Once you get the hang of running on a virtual machine, use Puppet or Chef to learn how to automatically configure your servers when starting a new VM. This will save you a lot of time setting up your public VPS later.

An important difference between your local virtual machine and a VPS is that you will have to take some steps to secure a publically accessible server. Points to take into consideration here are: key vs password based SSH authentication, iptables firewall.

I've found the Linode library to be a good source of introductory documentation about setting up a VPS: http://library.linode.com