A VPS, also known as Virtual Private Server is your own dedicated slice of a dedicated server. It's popular for people who have outgrown shared hosting, but don't want to go full in and purchase their own dedicated server.
With a VPS, you are allowed a certain amount of resources (based on the plan you purchase) unlike shared hosting where you are sharing the server with thousands of other websites.
These servers are fresh Operating system installations, with nothing but minimum packages to run a server. There you are free to install any package or software you want, you need to be proficient using the Linux command line.
For more information about VPS's can be found at http://en.wikipedia.org/wiki/Virtual_private_server