Quando você não quiser usar o campo de pesquisa no Ubuntu Software Center, você pode procurar os pacotes via apt com este comando: sudo apt-cache search virtualbox
Você receberá uma lista de pacotes encontrados e agora poderá instalá-lo digitando o pacote correto, por exemplo, sudo apt-get install virtualbox-4.2