So.. been trying to get a legacy rails app working and had this error..
after googling for a while, most people got this fixed using a gem install mysql -- --with command, or by copying an installed dll to the ruby bin directory.
However, what fixed it for me was:
sudo apt-get install libmysql-ruby
if you stumbled upon this, i hope it helped!