Can't exec "mysql_config": No such file or directory at Makefile.PL line 88.

apt-file can be a great help for such things. I often get errors about missing .h files and don't know which package they are in, but usually I find them with apt-file.
% apt-file search mysql_config
It also takes regular expressions.