gcc je součástí build-essential balíček, který byste měli nainstalovat před čímkoli jiným:
sudo apt-get install build-essential
AKTUALIZACE: Podle návrhu @bosnjak možná budete muset nainstalovat vývojářské nástroje openssl:
sudo apt-get install libssl-dev