Basically if after configuring your database in settings.py and running python manage.py dbshell you get a bunch of errors, you have a minor amount of installation work to do to get things rolling.
First thing I did was install pip, which is a better version of/replacement for easy_install:
sudo easy_install pip
Next I ran pip upgrade for good measure (probably not necessary but can't hurt, and worth running if you already had pip installed):
sudo pip install pip --upgrade
On my machine (Ubuntu 12.04 64-bit) I also had to build the dependencies for the python-mysqldb libraries:
sudo apt-get build-dep python-mysqldb
And finally with that in place you can use pip to install the Python MySQL libraries:
sudo pip install MySQL-python
If everything worked you should now be able to run python manage.py dbshell from your Django project and have it load up the MySQL console.