Para ter certeza de ter o repositório universe, onde o pacote do programa gimp é armazenado, execute (em uma janela de terminal)
sudo add-apt-repository universe
Em seguida, execute
sudo apt-get update
e se você tiver um sistema instalado (mas não se tiver um sistema ao vivo ou persistente)
sudo apt-get dist-upgrade
Por fim, instale o gimp com
sudo apt-get install gimp