This is an old thread, but if you google the error message, it appears first in the list of results, so it's worth writing a summary.
The root of the problem is that to install the mysql gem you need to compile some native code. ("Native code" is software written in a language such as C or C++ which needs to be compiled specifically for the processor that your computer uses - 64-bit Intel x86 or whatever.)
Actually, it's worth noting that this applies to EVERY DATABASE GEM - postgres, firebird or whatever. Mysql is just the most popular.
As far as I can see, the reason that the first solution above doesn't work is that it depends upon the method that you use to install mysql. On my Ubuntu Linux system, I did this:
sudo apt-get install mysql-server mysql-client
This installs mysql, but it doesn't create a directory /usr/local/mysql/bin/mysql_config. The first solution above expects that directory to exist.
The second solution is to install the dev client, which I did:
sudo apt-get install libmysqld-dev
and then I could install the mysql gem:
gem install mysql2
So the first solution didn't work for me but the second one did. However, for you it may be different.
It's also worth saying that I've installed mysql and Rails on a Windows PC and I didn't get this problem. It all depends on the environment you are using, the version of rails and the method used to install mysql.
This may not be under your control. Last year I tried to get my app working on a shared managed host that supported Ruby on Rails. They had just upgraded from Rails 2 to Rails 3. It being a manged host, they installed all the base software and when I hit this problem I couldn't get past it. I wasted hours and got through several hosting companies before I switched to a Virtual Private Server (VPS) where I have root access and install everything myself. I got the problem again, but this time I was able to get to the bottom of it.
If you working with a Linux host, this command may be useful:
find / -name "libmysqlclient.*" 2>/dev/null
It searches through your file system starting at the root looking for libmysqlclient. On my system it produces:
/usr/lib/libmysqlclient.a /usr/lib/libmysqlclient.so.16 /usr/lib/libmysqlclient.so /usr/lib/libmysqlclient.so.16.0.0
