I recently got a new Mac, and wanted a Virtual Machine solution. I read on the forums that there is no VMWare Player for OS-X, and I didn't want to pay for VMWare Fusion, so VirtualBox was my answer.
When I built my Windows and Linux VMs, I couldn't figure out why Full-Screen mode wouldn't work. Then I found that you have to install "Virtual Box Guest Additions" to get full screen mode to work. Installing this in both Windows and Linux was as easy as hitting HOST+D. This popped up a CD with the software, and installed it easily. Then, to enter/exit Full Screen mode, I just hit HOST+F. Simple as pie!