Instalación de MySQL:ERROR:No se pudo construir la extensión nativa de la gema

En los sistemas Debian (o Ubuntu), simplemente instale el paquete libmysqlclient-dev usando:

sudo apt-get install libmysqlclient-dev

y luego:

gem install mysql

Se instalará sin ningún error.