This is partially for me in the future just in case I'm stuck doing this again, and it's partially for the lone googler in the future who comes by needing a quick fix.
So, the short version:
Grab the 64bit version from MySQL ("Mac OS X 10.5 (x86_64)"). Easiest way is to grab the DMG, use the installer, and then add the preference pane.
It's probably helpful to add an alias for mysql in your ~/.profile:
alias mysql=/usr/local/mysql/bin/mysql
alias mysqladmin=/usr/local/mysql/bin/mysqladmin
Grab your Leopard DVD and install Xcode if you haven't already... it'll help you compile some of the native C code involved with the MySQL gem.
Rock this:
sudo env ARCHFLAGS="-Os -arch x86_64 -fno-common" gem install mysql -- --with-mysql-config=/usr/local/mysql/bin/mysql_config
That'll build your MySQL gem for you. Most of the issues with errors like "lazy symbol binding failed" are the result of not setting those architecture flags; something with Leopard pushing multiple architectures but MySQL expecting only one.
Those are the main sticklers; if I missed a step along the way it's probably easy enough that a quick Googling would solve. Kudos to http://cho.hapgoods.com/wordpress/?p=158 and its commenters in helping figure out some of those pesky details.