There are a lot of things which are called "Virtual private servers" or "Virtual dedicated servers" which actually vary considerably in what they're offering.
In one camp are the "true VM" people who are running the likes of VMWare, user mode Linux, Xen, Virtual PC etc.
In another are the fake ones which provide various types of "partitioning" system which run a single OS kernel to make it appear as the machine's yours.
Generally speaking, the fake ones won't give you the same degree of control.
Typically, you'd want to be able to install any version of any web server or application server you want (given the limitations of the virtual hardware, i.e. memory).
But some have hacky partitioning systems which don't let you do that. Find out exactly what they're offering.
Mark