The implementation of the virtual machine is a kernel for the kernel.
In a typical operating system, there is application code (aka "userland") and kernel code. They use the same set of instructions; however, the CPU knows, at any time, whether it is executing application or kernel code. When application code tries to execute some opcodes which access the hardware (the
out opcodes for x86), the CPU traps: it temporarily jumps to kernel code (the address of that code is registered in a specific table). The kernel code decides what to do with the access (grant it, modify it, kill the application process...). If the kernel code decides to grant the access, or the kernel blocks it but pretends to have performed it, then application code can believe that it could access the hardware directly.
Similarly, when application code reads or writes data in memory, it uses an abstraction of memory: a virtual address space which is mapped to physical memory (or not...) through the MMU. The MMU uses tables that the kernel fills (and, of course, the kernel takes care not to make these tables part of the address space visible from the application code). This way, the application is in a magical world where it is alone in a big address space, whereas in reality there are several concurrently executed applications, which cannot see each other.
A virtual machine uses the same structure, one level up. When the kernel accesses the hardware or the MMU, it actually is under scrutiny of the virtual machine implementation (the hypervisor) which traps unwanted accesses.
Particulars vary quite a lot. The main distinction is whether the kernel is aware that it runs in a virtual machine or not. With Xen, the kernel is aware; it knows that it is under control of a superior deity (the hypervisor) and does not try to tap into the hardware directly; instead, it asks nicely through a dedicated interface. With VirtualBox, the kernel is not aware; the guest operating system believes that it runs on true hardware, and the VM works hard to maintain the illusion.
Other differences can be made on the means by which virtualization is enforced (i.e. how the hypervisor can trap kernel code). Recent x86 processors offer some specific support with dedicated opcodes. Older x86 processors, in 32-bit mode, can use the various remnants of older protection mechanisms (segment registers and the four "rings", mostly)(these have been removed from 64-bit mode, which is why 64-bit VM must use AMD-V/VT-x). Other techniques include emulating each virtualized opcode (for the whole of the emulated machine, or parts of it), possibly with more-or-less dynamic translation (aka JIT compilation), aas QEMU does in cross-CPU situations.
There is a whole paraphernalia of terms on the subject (virtualization, paravirtualization, emulation, simulation, hypervisor...) which is not completely consensual, and often quite byzantine. Some readers who cling to some specific doctrines of terminology have probably been somewhat irritated by the loose way I use the terms.