gcc faz parte do build-essential pacote, que você deve instalar antes de qualquer outra coisa:sudo apt-get install build-essential
ATUALIZAÇÃO: Seguindo a sugestão do @bosnjak, você também pode precisar instalar as ferramentas do desenvolvedor openssl:
sudo apt-get install libssl-dev
