With OS X you have a few extra parameters you need to pass along. Here, I'm installing an older version of the mysql gem pointing it to the mysql_config file that resides in my current mysql version (5.1.51). Your path may vary but it shouldn't vary a lot.
sudo env ARCHFLAGS="-arch x86_64" gem install -v=2.7 mysql -- --with-mysql-config=/usr/local/Cellar/mysql/5.1.51/bin/mysql_config
Remove the -v=2.7 to get the latest version instead (2.8.1) or better yet, use the mysql2 gem if you can.