MySQLのインストールは64ビット（Windowsなど）だと思いますよね？
Rubyは32ビットであるため、32ビットを64ビットにリンクすることはできません 。
インストール手順をカバーする記事をブログに投稿しました：
http://blog.mmediasys.com/2011/07/07/installing-mysql-on-windows-7-x64-and-using-ruby-with-it/
これらの手順では、MySQL Connector / Cを使用して、32ビットと64ビットの問題を回避します。
両方のmysql またはmysql2 gemはこれで動作するはずです。