Você precisa de bibliotecas de desenvolvimento python para criar módulos python:
sudo apt install python3-dev libpython3-dev
deve cuidar disso para você.
Mas a maneira recomendada de adicionar isso no Ubuntu seria usar os repositórios do Ubuntu. Assim, para instalar as ligações do mysql para python3, execute
sudo apt install python3-mysqldb
Isto irá instalar as ligações necessárias para se conectar ao mysql do Python 3, e garante que ele será atualizado junto com outros pacotes do seu sistema. Isso é recomendado, a menos que você precise especificamente de uma versão mais recente, ou o pacote não esteja disponível nos repositórios do Ubuntu.