NOTE: updated January 2010
If you don't have the mySQL development libraries installed then you might want to install them.
Make sure you have the DEV libraries installed on the linux box and then run this command
apt-get install libmysqlclient*-dev
It work for me on CentOS 5.3 just today.
gem install mysql --no-rdoc --no-ri -- --with-mysql-config=/usr/bin/mysql_config