How can I install a 64bit Linux virtual machine on a 32bit Linux?
Both VMware and VirtualBox can run a 64-bit virtual machine on a 32-bit host system, if you have a 64-bit processor. For VirtualBox, your processor must have hardware virtualization support (either AMD-V or VT-x, shown as svm and vmx in the flags: line of /proc/cpuinfo under Linux); most x86-64 processors except for the earlier ones, and in particular I think all core i5 models, have this support.
Failing that, you can use a virtual machine technology that emulates an x86-64 processor in software, such as Qemu. But it's not a good idea if you don't need it: it's slow, memory-hungry, and awkward.
My recommendation is to just get a 64-bit host or at least a 64-bit kernel. You can run 32-bit applications on an x86-64 (a.k.a. amd64) kernel, in fact you can run a wholly 32-bit Linux userland on an amd64 Linux kernel.
Ubuntu doesn't provide a 64-bit kernel in its i386 distribution (Debian does). You can grab the kernel from the amd64 distribution, and applications should just run, but under natty the package isn't easily installable.
So the easiest route to running 64-bit applications would be make a parallel installation of an amd64 Ubuntu. Install it on a separate partition, keeping your existing 32-bit installation as well. In the 64-bit system, mount the existing partitions, then set up a 32-bit schroot (see this guide)) to run 32-bit programs.
Gilles points out that I was mistaken about VirtualBox and VMware supporting 64-bit guests on 32-bit hosts. VirtualBox is available in the Ubuntu repositories in the virtualbox-ose package.
VirtualBox's documentation provides the following advice regarding running 64-bit operating systems:
VirtualBox supports 64-bit guest operating systems, even on 32-bit host operating systems, provided that the following conditions are met:
You need a 64-bit processor with hardware virtualization support (see the section called “Hardware vs. software virtualization”). [Your processor meets this requirement.]
You must enable hardware virtualization for the particular VM for which you want 64-bit support; software virtualization is not supported for 64-bit VMs.
If you want to use 64-bit guest support on a 32-bit host operating system, you must also select a 64-bit operating system for the particular VM. Since supporting 64 bits on 32-bit hosts incurs additional overhead, VirtualBox only enables this support upon explicit request.
On 64-bit hosts (which typically come with hardware virtualization support), 64-bit guest operating systems are always supported regardless of settings, so you can simply install a 64-bit operating system in the guest.
Warning
On any host, you should enable the I/O APIC for virtual machines that you intend to use in 64-bit mode. This is especially true for 64-bit Windows VMs. See the section called “"Advanced" tab”. In addition, for 64-bit Windows guests, you should make sure that the VM uses the Intel networking device, since there is no 64-bit driver support for the AMD PCNet card; see the section called “Virtual networking hardware”. If you use the "Create VM" wizard of the VirtualBox graphical user interface (see the section called “Creating your first virtual machine”), VirtualBox will automatically use the correct settings for each selected 64-bit operating system type.
If you must use software virtualization, you can install the qemu package from the Ubuntu repositories. There are several GUI packages available to control it (I prefer aqemu), but you can also use it from the command line.
Alternatively, consider running a 64-bit version of Linux instead. Ubuntu x86_64 supports running 32-bit binaries without any virtualization whatsoever.