Su Ubuntu si consiglia di utilizzare il repository delle distribuzioni. Quindi l'installazione di python-mysqldb dovrebbe essere semplice:
sudo apt-get install python-mysqldb
Se desideri effettivamente utilizzare pip per l'installazione, che come accennato in precedenza non è il percorso suggerito ma possibile, dai un'occhiata a questa domanda e risposta posta in precedenza:pip install mysql-python non riesce con EnvironmentError:mysql_config non trovato
Ecco una guida molto completa dello sviluppatore:http://mysql-python.blogspot.no/2012/11/is-mysqldb-hard-to-install.html
Per ottenere tutti i prerequisiti per python-mysqld per installarlo usando pip (cosa che vorrai fare se stai usando virtualenv), esegui questo:
sudo apt-get install build-essential python-dev libmysqlclient-dev