After having trouble installing mysql support for python, I ran into similar problems with ruby. To fix, first I installed a new version of MySQL from mysql.com. I'm not sure if this is necessary since OS X comes with MySQL but I don't have a second box to test with. After running the install, pick one of the lines below that matches the version you installed.
sudo env ARCHFLAGS="-arch i386" gem install mysql -- \ --with-mysql-include=/usr/local/mysql/include \ --with-mysql-lib=/usr/local/mysql/lib
sudo env ARCHFLAGS="-arch x86_64" gem install mysql -- \ --with-mysql-include=/usr/local/mysql/include \ --with-mysql-lib=/usr/local/mysql/lib
* I had problems using the x86_64 version because ruby is only compiled as 32-bit