Нито един от съществуващите отговори не работи за мен на Ubuntu Server 16.04, така че стартирах:
sudo apt-get install libmysqlclient-dev
sudo -H pip3 install mysqlclient
Първата команда ми даде конфигурацията на mysql, необходима за втората команда.