There are two versions of VirtualBox available, the Open Source Edition and the free, but proprietary, Personal Use / Evaluation License version. This closed-source version has a few additional features, such as USB support. Installing VirtualBox OSE (Open Source Edition) is easiest. Search for virtualbox-ose package in UbuntuHelp:synaptic, aptitude or whichever package manager you use, or use this link|apt:virtualbox-ose|this link. To install the proprietary VirtualBox package, visit:  See VirtualBox/Previous for information on detailed instructions for older versions of Ubuntu and Virtualbox.
There is a known issue with VirtualBox and the Ubuntu 8.04 and later Server releases. The server release requires the PAE extension to be available on the virtual processor presented by VirtualBox to the guest OS. PAE support on the virtual processor is available in VirtualBox, but must be enabled on a per processor basis. This is done either through the GUI,
Vm's Settings > General Section > Advanced Tab > Enable PAE/NX
or with the command
VBoxManage modifyvm <VM name> -pae on
This article is also valid for Ubuntu 8.10 Intrepid Ibex
64 bit guests
A 64 bit host CPU is not enough to run 64 bit guests (in contrast to VMWare). It must also have virtualization extensions.