This one had me for a while: When attempting to install the MySQL gem on my shiny new Slicehost slice, I was getting the folowing error:

Building native extensions.  This could take a while...
ERROR:  Error installing mysql:
   ERROR: Failed to build gem native extension.

/usr/local/bin/ruby extconf.rb install mysql -- --with-mysql-include=/usr/include/mysql --with-mysql-lib=/usr/lib/mysql
checking for mysql_query() in -lmysqlclient... no
checking for main() in -lm... yes
checking for mysql_query() in -lmysqlclient... no
checking for main() in -lz... yes
checking for mysql_query() in -lmysqlclient... no
checking for main() in -lsocket... no
checking for mysql_query() in -lmysqlclient... no
checking for main() in -lnsl... yes
checking for mysql_query() in -lmysqlclient... no
*** extconf.rb failed ***
Could not create Makefile due to some reason, probably lack of
necessary libraries and/or headers.  Check the mkmf.log file for more
details.  You may need configuration options.

Provided configuration options:
   --with-opt-dir
   --without-opt-dir
   --with-opt-include
   --without-opt-include=${opt-dir}/include
   --with-opt-lib
   --without-opt-lib=${opt-dir}/lib
   --with-make-prog
   --without-make-prog
   --srcdir=.
   --curdir
   --ruby=/usr/local/bin/ruby
   --with-mysql-config
   --without-mysql-config
   --with-mysql-dir
   --without-mysql-dir
   --with-mysql-include=${mysql-dir}/include
   --with-mysql-lib=${mysql-dir}/lib
   --with-mysqlclientlib
   --without-mysqlclientlib
   --with-mlib
   --without-mlib
   --with-mysqlclientlib
   --without-mysqlclientlib
   --with-zlib
   --without-zlib
   --with-mysqlclientlib
   --without-mysqlclientlib
   --with-socketlib
   --without-socketlib
   --with-mysqlclientlib
   --without-mysqlclientlib
   --with-nsllib
   --without-nsllib
   --with-mysqlclientlib
   --without-mysqlclientlib

Gem files will remain installed in /usr/local/lib/ruby/gems/1.8/gems/mysql-2.7 for inspection.
Results logged to /usr/local/lib/ruby/gems/1.8/gems/mysql-2.7/gem_make.out

It turns out, all I needed was to run the following:

gem install mysql -- --with-mysql-config=/usr/bin/mysql_config

Hope this saves someone the hour or so I spent scratching my head!