How to compact VirtualBox's VDI file size?

You have to do the following steps:

1. Run defrag in the guest (Windows only)
2. Nullify free space:
   With a Linux Guest run this:

   sudo dd if=/dev/zero | pv | sudo dd of=/bigemptyfile bs=4096k
   sudo rm -rf /bigemptyfile
   

   Or:

   telinit 1
   mount -o remount,ro /dev/sda1
   zerofree -v /dev/sda1
   

   With a Windows Guest, download SDelete from Sysinternals and run this:

   sdelete.exe c: -z
   

   (replace C: with the drive letter of the VDI)
3. Shutdown the guest VM
4. Now run VBoxManage's modifyhd command with the --compact option:
   With a Linux Host run this:

   vboxmanage modifyhd /path/to/thedisk.vdi --compact
   

   With a Windows Host run this:

   VBoxManage.exe modifyhd c:\path\to\thedisk.vdi --compact
   

   With a Mac Host run this:

   VBoxManage modifyhd /path/to/thedisk.vdi --compact
   

This reduces the vdi size.

EDIT:

New versions of VirtualBox map modifyhd and modifyvdi to modifymedium; Source.