The easiest method doesn't require removing your virtual machines and mucking up their settings.
Copy your Virtualbox VMs folder to a new drive.
Run the Virtual Box Machine Manager. Run the media Manager File -> Virtual Media Manager
2a. Choose the VM to move storage for. Click the Release button and then the Remove button. On the next dialog, you can either remove or keep the virtual drive. Close the manager leaving you in your Virtualbox Machine Manager.
Select the VM you just removed media for, click the Settings button, Click the Storage section. Add a controller for the media (SATA usually) and then add a hard drive and choose existing disk and select the VD at your new location.
Repeat for each machine you're moving
Fire off your virtual machine at the new location to check. Next time you visit the Virtual Media Manager, hovering over the VM entry will show you where the VD is stored.
Make sure you change your snapshots folders to point to the new drive if you're using them. Each machine has a snapshot folder setting and the VM Manager has a Default Machine folder setting in File -> Settings that needs to be changed as well.
In addition I had to also modify path in xml file. After that it worked flawlessly.
NOTE: Things have changed a bit since this was written, see Rob's answer. It's extremely simple now.
Why don't you want to edit your VirtualBox.xml manually? I think it is by far the easiest option. – hugo der hungrige – 2014-10-01T19:32:05.883
@hugoderhungrige No idea, it's too long ago. I guess, I mis-edited it once, you know once bitten, twice shy... – maaartinus – 2014-10-01T19:40:13.043
@maaartinus still interesting today though :) – hugo der hungrige – 2014-10-02T09:30:58.533
4Awww, I was going to suggest symlinks (they solve Everything™), but you've blocked that idea... :( – DMA57361 – 2011-03-11T11:03:57.113
2I don't trust links on Windows at all. While NTFS is capable of it, Windows XP knows nothing about it and there are enough problems with it already. I may be needlessly coward... – maaartinus – 2011-03-11T11:25:25.793
Ah, yeah, I wouldn't touch them on XP. But support on 7 is pretty solid - you still have to build them from the cmd line, but that's not really much of a chore. I'm not sure about Vista... – DMA57361 – 2011-03-11T11:32:27.383
It's even worse, XP version of NTFS does support hardlinks, but these cannot span volumes. Obviously, I wanted to move the data to a different partition.
– maaartinus – 2011-03-11T12:13:15.270Hardlinks can't ever span volumes, only symlinks can (and can be used for this sort of thing, my user folders are all symlinked to my second HDD, for example). But, personally I'd still avoid hardlinks in XP (even if they were an option). – DMA57361 – 2011-03-11T12:16:30.367