Right now it looks like his blog is down so I can't finish this writeup!
The process is pretty easy though. Since mySQL is already listed in normal debian repositories, you can just run a few generic commands and fix any dependencies as you go!
SSH into your pi [windows users use putty]
apt-get install mysql-server mysql-client
mysqladmin -u root -h localhost password 'your root password here'
mysqladmin -u root -h 'your hostname here' password 'your root password here'
mysql -u root -p
This should ask you for the password you just set up and the mySQL terminal interface will appear.
You now have mySQL running on your Pi!!!
I don't think I have the mySQL skills yet to write up an effective guide for configuring a new database from scratch on the command line. However, you should be able to do it pretty easily. You are already 99% of the way there. The only remaining steps to synchronize your XBMC installations are creation of a new database, uploading a config.xml to each XBMC box, and populating the database by scanning in a new library. Check out the XBMC wiki on the subject.