Ok, after 20 pages of tests, its time to draw some conclusions.
To me, it seem that VMware and VirtualBox are the fastest virtual machine across the board. They have good CPU/memory performance, good disk access time and good network layer speed.
KVM is, instead, a mixed beast: it has quite good CPU/memory and network speed, but it fail in the crucial I/O subsystem performance more often than not.
Xen is at the opposite end of the spectrum: it as respectable I/O access time but quite bad CPU/memory performance that, in turn, can badly influence network speed and CPU load also.
Speaking about interfaces, VirtualBox has an excellent Qt-based interface and a well developped CLI. Xen and KVM utilize the virt-manager interface (GTK+ based), which is very well done and also provide a robust CLI to play with. VMware is the only that does not provide a standalone graphical interface, substituting it with a Web-based UI. While this is a very good idea in principle, we must underline a very annoying fact about the web interface: it is quite unresponsive and very unstable. On CentOS/RedHat 5.4 you must manually install a libc dynamic library file to let the WebUI "survive" more than just some clicks from the user (read this bug report for details: http://bugs.centos.org/view.php?id=3884 ). On the other hand, VMware probably has the best developped CLI, with Perl and C bindings.
So, who is the winner of the day? Let me repeat: each of the examined virtualizer has its reasons to exist, with its strong points but also with some drawbacks.
However, if I am forced to pick just one of these softwares for a dedicated server machine, I will probably go with VMware: while VirtualBox is quite on par, I think that VMware's paravirtualized network driver give it a slight advantage over the others. Note however that VMware server has some important handicaps: it can manage only 2 snapshots and, as stated above, the WebUI has some problems running on CentOS 5.4. So, if you plan to heavily use the snapshot features, you must use the latest CentOS/RedHat release (5.4) and/or you want a desktop-oriented virtualizer, go with VirtualBox: it has excellent performances and an easy-to-use interface.
If you, instead, love the Linux-standard virtmanager interface, you can go with KVM or Xen. All in all, I would prefer KVM most often that Xen because the latter seems to be very slow in CPU and memory subsystems. Moreover, Xen seems to have some serious problem with massive-multithreaded programs, which is not so good for a server machine.
UPDATE 06/30/2010: the increasing incompatibilities between VMware server 2.0.2 and CentOS 5.4 and later forced us to stop using VMware on our primary virtualization server. Now we're using VirtualBox, coupled with some in-house made scripts to manage the autostart / stop / backup of the virtual machines. So, for a new Linux installation, I would now prefer using VirtualBox vs VMware server.
UPDATE 03/22/2011: a recent article comparing KVM vs VirtualBox can be found here: http://www.ilsistemista.net/index.php/virtualization/12-kvm-vs-virtualbox-40-on-rhel-6.html