Dificultades para instalar mysql gem en Ubuntu

Pruebe esto y luego instale la gema mysql:

sudo apt-get install libmysqlclient-dev 

Si eso no es suficiente, pruébalo así

 sudo apt-get install libmysqlclient-dev libmysqlclient16 ruby-dev