As I always seem to forget the package name required to install the mySQL gem and get this error...
ERROR: While executing gem ... (RuntimeError)
ERROR: Failed to build gem native extension.
Gem files will remain installed in /usr/lib/ruby/gems/1.8/gems/mysql-2.8.1 for inspection.
The fix is as simple as...
sudo apt-get install libmysqlclient-dev
Problem solved.