Firstly, what is the name of virtual machine that you want to do this with?
You can list the names of your VMs in a terminal as below
$ VBoxManage list -l vms|grep "Guest OS" -B1...and choose the name of your virtual machine.
For this example my VM is called 'Windows XP' and my host is running Ubuntu 9.10, other distros running Gnome shouldn't be much different.
To autostart your VM upon login to Gnome...
Launch System > Preference > Startup Applications, select the Add button.
Then enter a name for the program in the Name: field and in the Command field enter;
VBoxManage startvm "Your VM Name"Replacing the 'Your VM Name' with the name of your VM, if there are spaces in the name your will need the quotes.
Lastly to have your system cleanly stop your running VMs for you when you shut down your Linux box you can edit the vboxdrv init script. To do this you will need root privileges.
You have the choice of 3 methods of stopping the VM, a poweroff, an acpi button emulation or my preference, a savestate shutdown which will stop the VM and preserve it's runtime state, it will then resume the next time it is started.
Edit the init script with the nano text editor, if you have sudo setup or if you're using an Ubuntu/Debian style Linux distribution...
$ sudo nano /etc/init.d/vboxdrv... and enter your password.
If you don't use sudo, you can su to root before running nano or you can use su as below..
$ su root -c nano /etc/init.d/vboxdrv... and enter the root account's password.
In nano hit [Ctrl]+[W] to search and enter SHUTDOWN in caps. This will take you line 235.
A few lines down uncomment the appropriate "SHUTDOWN=" line of choice, for example to choose a savestate shutdown edit the line;
# SHUTDOWN=savestateto read,
SHUTDOWN=savestateThen hit [Ctrl]+[O] to save the change, then [Ctrl]+[X] to exit nano.
This will ensure that your system when shut down will cleanly stop your running VMs without you having to do so manually.