Here’s how to import the appropriate key in ubuntu:

apt-key adv --keyserver keyserver.ubuntu.com --recv-keys $Key

Where $key == the gpg key id. The key id is shown in the error message you get when running apt-get update after adding a new repository. For example:

GPG error: http://download.virtualbox.org karmic Release: The following signatures couldn't be verified because the public key is not available: NO_PUBKEY DCF9F87B6DFBCBAE

DCF9F87B6DFBCBAE is the key ID for the virtualbox karmic repository. So doing this:

apt-key adv --keyserver keyserver.ubuntu.com --recv-keys DCF9F87B6DFBCBAE

imports the correct key.