How to make a distro be fullscreen on VirtualBox?

There are a few things that need to be in place. You need to have guest additions installed on the guest OS. You have to have "guest display auto-resize" feature enabled (Host+g toggles this), and then you have to actually activate full-screen mode (Host+f toggles this).

Specifically, on the Debian/Ubuntu guest, run the following (as root):

apt-get install virtualbox-ose-guest-x11