Most likely, what you want to do is add charset='utf8' to your MySQLdb.connect() call.
For MySQL itself, character sets are set separately in many different contexts - most notably, for both table storage and for connections (and MySQL unfortunately still seems to default to latin-1 in many cases). So, you can - for example - go to the trouble of setting your entire database to use UTF-8:
CREATE DATABASE somedatabase DEFAULT CHARACTER SET utf8 COLLATE utf8_bin;
And yet, when you connect a client, MySQL may still think you're communicating with it in some other encoding:
mysql> show variables like 'character_set%';
+--------------------------+----------------------------+
| Variable_name | Value |
+--------------------------+----------------------------+
| character_set_client | latin1 |
| character_set_connection | latin1 |
| character_set_database | utf8 |
| character_set_filesystem | binary |
| character_set_results | latin1 |
| character_set_server | latin1 |
| character_set_system | utf8 |
| character_sets_dir | /usr/share/mysql/charsets/ |
+--------------------------+----------------------------+
A basic solution to this is to execute SET NAMES UTF8 immediately upon connecting, before you do anything else:
mysql> SET NAMES UTF8;
mysql> show variables like 'character_set%';
+--------------------------+----------------------------+
| Variable_name | Value |
+--------------------------+----------------------------+
| character_set_client | utf8 |
| character_set_connection | utf8 |
| character_set_database | utf8 |
| character_set_filesystem | binary |
| character_set_results | utf8 |
| character_set_server | latin1 |
| character_set_system | utf8 |
| character_sets_dir | /usr/share/mysql/charsets/ |
+--------------------------+----------------------------+
However, in your case, this still isn't sufficient, because the python MySQLdb module itself also wants to be helpful and automatically encode/decode python's native unicode strings for you. So, you have to set the character set in MySQLdb. This is best done, as mentioned earlier, by passing charset='utf8' when creating your MySQLdb connection. (This will also cause MySQLdb to inform the mysql server that your connection is using UTF8, so you do not need to run SET NAMES UTF8 directly)
MySQLdb.connectwithuse_unicode = True?