There are several implementations of Virtual Server software for Linux. These include Xen, SW-Soft's Virtuozzo, and the now rather elderly User-Mode Linux (UML).
Virtuozzo is a product of SW-Soft, and it doesn't allow users to pick and choose their own operating systems to run within their virtual servers. The company instead comes up with a well-tested OS kernel, and that kernel runs on every VDS. Virtuozzo also provides a great utility called the Power Panel, which allows a user to examine the performance of their virtual server using a web-based interface. Users can stop, start, repair, and re-format their VDS from a web browser. This is great if you'd like to do some experimentation on your VDS, but don't want to have to call your host's tech support to bail you out if you go a bit too far and really break something.
Both major types of VPS have their proponents, and both types have had some growing pains along the way. Some of the major cheerleaders of UML are former Virtuozzo customers who were victims of software bugs which have long since been fixed. Other Virtuozzo supporters claim that it is much more easy for users to degrade performance on a UML-based VPS. I've used both platforms, and don't see a clear winner. The Power Panel is a nice utility in favour of Virtuozzo, but many UML hosts provide similar functions using custom web panel interfaces.
User-Mode Linux was designed to allow many of the administrative functions of the operating system, traditionally executed by the Linux kernel in a special mode, to be accessible to ordinary users. This allows the normally privileged operating system to extend its behaviour such that user programs can not only use the resources that they are provided with, but also to emulate the operating system in controlling the resources that they are given. Basically, every user runs two operating systems, the main one, which is controlling the entire server, and belongs to (and is controlled by) the administrator, and the OS of their choice, which runs on their virtual server. This may seem dry and boring, but it allows the users of UML virtual servers to choose their OS. On a particular machine, in which the administrator might have installed CentOS Linux, users might be running virtual servers which use Gentoo Linux, Fedora Linux and Suse Linux simultaneously.