Looks like it can't find the MySQL libraries to build the native extension. You can find out where the libs and includes are installed by running
mysql_config --libs --include
which will produce something like
-rdynamic -L/usr/local/mysql/lib -lmysqlclient -lz -lcrypt -lnsl -lm -lmygcc
-I/usr/local/mysql/include
Then with the -L option(location of the mysql libraries) and the -I option(location of the mysql include files) you can install the gem like this
gem install mysql -- --with-mysql-include=/usr/local/mysql/include --with-mysql-lib=/usr/local/mysql/lib
Obviously the paths for your install will be different, but hopefully you get the idea.