How can I start a VM without getting a window?

Old question, but an update is in order:

As of VirtualBox 4.2, you can start a headless machine from the GUI by holding Shift while you click the Start button.

Horribly unintuitive, but that, and other new features, are outlined in an Oracle blog post.

EDIT: As of VirtualBox 5.0, there's a dropdown on the Start button that allows you to choose how to start the VM, including in headless mode.

First, make sure that the Virtual Box binaries are in your path. This is done by default on Linux, but in Windows, you might have to manually add the installation directory's bin folder to your path.

Then, you need to know either your Guest OS name or UUID number. You can find both of these by typing

VBoxManage list vms

into a terminal. From there, simply type

VBoxHeadless -s <Guest-OS-Name>

or

VBoxHeadless -s <UUID>

This launches the VM without attaching its display to a window. Now all you have to do is set this command as a boot-time service that runs in the background, and you'll be set.

You can tell VirtualBox to start the VM in headless mode, not using the gui start button - but its the same.

VBoxManage startvm <guest-os-name> --type headless