No Ubuntu é aconselhável usar o repositório de distribuições. Portanto, a instalação do python-mysqldb deve ser direta:
sudo apt-get install python-mysqldb
Se você realmente deseja usar o pip para instalar, que é, como mencionado antes, não o caminho sugerido, mas possível, dê uma olhada nesta pergunta e resposta anteriores:pip install mysql-python falha com EnvironmentError:mysql_config não encontrado
Aqui está um guia muito completo do desenvolvedor:http://mysql-python.blogspot.no/2012/11/is-mysqldb-hard-to-install.html
Para obter todos os pré-requisitos para python-mysqld instalá-lo usando pip (o que você desejará fazer se estiver usando virtualenv), execute isto:
sudo apt-get install build-essential python-dev libmysqlclient-dev
