When you start VirtualBox, you should see a screen like this. You don't need to change anything yet; just click the "New" button in the top left corner.
Now you need to tell VirtualBox what kind of OS you're running. The program adjusts a number of settings when you specify an OS, but this is most important for installing Guest Additions, which I'll discuss later.
Next, you'll be asked how much RAM you want to allocate to your guest OS. This is up to you, but use the minimum recommended RAM for each OS as rough guidance. If you're planning on doing heavy-duty work on your guest OS, like running Photoshop for example, you should allocate more—but remember, any RAM you give to your guest OS is effectively stolen from your host, or main, OS. Don't stress too much over this, you can adjust to taste later.
Now you've got to create a virtual hard drive. This will appear as the main hard drive to your guest OS. Create a new disk, and make sure "Boot Primary Disk" is checked.
Set how much space you want your guest OS to have. Pretend this is a real hard drive, because to your virtual machine, that's exactly what it'll look like is. In other words, make sure you have enough space to install your OS's base files, plus whatever apps you might want to download later. You can create a dynamically adjusting disk which gets larger as you need it, but I've had my share of problems with this; you're best off getting your size right the first time around. 10GB should cover the bare basics in most situations, though you'll want much more if you plan on storing music, video and other media. Shared folders, which let the guest OS store files in the host machine's file system, are worth considering here; bigger files can just be stored there, leaving your virtual disk for the bare essentials.
Once your new (fake) hard drive is done formatting, you'll be returned to your VirtualBox home screen, which will now show list of your fledging guest OS(es). From here, you'll want to select your newly-created machines, and click "CD/DVD-ROM Drive."
This will bring you to a settings screen, where you need to tell VirtualBox where your OS install disc or OS image is. If you have a Windows CD or Linux install CD, select "Host CD/DVD Drive," and find your computer's optical drive in the pulldown menu. If you're installing from a downloaded ISO file, just select "ISO Image File," click the icon next to the dropdown menu, and open the image file. Click "OK."
Now, at your VirtualBox homescreen, select your virtual machine again and click "Start"
From here, the process is exactly like installing an OS natively. In other words, just follow your OS's install prompts.
When your OS asks where to be installed, it should automatically find virtual disk you've created for it. Make sure it's the same size you designated, then go ahead with the installation. The OS will take care of whatever partitioning and formatting it needs to.
Wait a while!
So yeah, that's it. Before you know it, you'll be booted to a new desktop, within your old one. It's kinda nuts.