gem install: Failed to build gem native extension (can't find header files)

For those who may be confused by the accepted answer, as I was, you also need to have the ruby headers installed [ruby-devel].

The article that saved my hide is here.

And this is the revised solution (note that I'm on Fedora 13):

yum -y install gcc mysql-devel ruby-devel rubygems
gem install -y mysql -- --with-mysql-config=/usr/bin/mysql_config

For Debian, and other distributions using Debian style packaging the ruby development headers are installed by:

sudo apt-get install ruby-dev

For Ubuntu the ruby development headers are installed by:

sudo apt-get install ruby-all-dev

If you are using a earlier version of ruby (such as 2.2), then you will need to run:

sudo apt-get install ruby2.2-dev

(where 2.2 is your desired Ruby version)

Red Hat, Fedora:

yum -y install gcc mysql-devel ruby-devel rubygems
gem install -y mysql -- --with-mysql-config=/usr/bin/mysql_config

Debian, Ubuntu:

apt-get install libmysqlclient-dev ruby-dev
gem install mysql

Arch Linux:

pacman -S libmariadbclient
gem install mysql

For anyone reading this in 2015: if you happened to install the package ruby2.0, you need to install the matching ruby2.0-dev to get the appropriate Ruby headers. The same goes for ruby2.1 and ruby2.2, etc. For example:

$ sudo apt-get install ruby2.2-dev