Installing Guest Additions from the GUI
After selecting Devices -> Install Guest Additions or by pressing Host+D from the Virtual Box Manager the Guest Additions CD .iso will be loaded but not installed in your guest OS.
GNOME classic (10.04 LTS)
To install the Guest Additions we will have a CD icon on our desktop as soon as the virtual drive is mounted:

Next step is to run the autorun.sh script (as root) on this mounted CD either by opening the drive or by choosing "Open With Autorun Prompt" from the right-click context menu as depicted above. This will build and install the vbox kernel modules needed.
Unity (> 11.04)
The guest additions is mounted as a virtual CD visible on the launcher:

In case the system is set up to autorun a CD it should just open the following autorun dialogue (if not select the CD symbol, choose open, then choose Open Autorun Prompt)

After having entered your credentials for root access the guest additions will build as seen from the terminal output:

Press Return to close the terminal.
Note 1
Guest Additions need a reboot of your guest OS to take effect.
Note 2
In some systems the Virtual Box Guest Additions CD icon may not be shown on the desktop, but will be accessible from the Places menu. If the CD still was not there you may have to manually add the VBoxGuestAdditions.iso as a CD-ROM in the Virtual Box Manager Storage menu. In an Ubuntu host the disk image is in /usr/share/virtualbox/VBoxGuestAdditions.iso.
Note 3
In case we installed an older version of Virtual Box from the Software Center we additionally have to install the package virtualbox-guest-additions from there.
Installing Guest Additions from a Terminal
In case Guest Additions are not installed properly we may not be able to boot to the GUI. In this case we need to boot holding the Shift key to access the Grub menu where we can choose recovery mode to select a root shell:

The Guest Additions .iso file needs to be installed on /dev/cdrom from the Virtual Box Manager (see above). We then may install Guest Additions by typing the following commands:
mount /dev/cdrom /mnt # or any other mountpoint
cd /mnt
./VBoxLinuxAdditions.run
reboot