Ruby De-Railed?

I'm having some issues... with Ruby On Rails. I installed MySQL 4.1 from the package at MySQL.com and for the life of me I can not install rb-mysql via gem or anything else. I get the following message:

ruby extconf.rb install mysql -- --with-mysql-include=/usr/local/mysql/include/ --with-mysql-lib=/usr/local/mysql/lib/nchecking for mysql_query() in -lmysqlclient... no
checking for main() in -lm... no
checking for mysql_query() in -lmysqlclient... no
checking for main() in -lz... no
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... no
checking for mysql_query() in -lmysqlclient... no

Any ideas what I can do to get it in? I'd really like to try a few things with RoR but this has been quite the stumbling block in the process.