Dê uma olhada neste Howto da Comunidade Ubuntu intitulado: AptGet / Howto , especificamente nesta seção, Configurando o apt-get para usar um http-proxy .
Você costuma definir essa variável de ambiente da seguinte forma:
$ export http_proxy=http://yourproxyaddress:proxyport
Você pode obter o valor do seu proxy fora do seu navegador, se você não o conhece, já que aparentemente está funcionando lá. Isso deve ser o suficiente para começar, há mais detalhes nesses links se você precisar deles.