First off, everyone I know thats a good MySQL DBA already has a job myself included. Occasionally I know of someone looking for a job, but more often than not, they end up finding a job rather quickly.
Obviously the best way to find people is word-of-mouth, and the next best way is to find an expert in the field and ask them who they recommend. I am flattered that you consider me an expert and are asking me! If I know of someone, I will definitely let you know. If not, I will probably direct you here.
So, what now? Well, the more people you contact, the better. Finding experts is the right step, and finding people that they know, who are interested in MySQL, is another right step. To that end, first consider your audience do you want someone who also has skills as a developer? As a sysadmin? As a manager? Find groups of experts or at least groups of eager learners near you.
Also, consider what you need. You may think you need a fulltime DBA but what do you really need? Maybe what you need is someone to make sure backups are running smoothly, help developers write new queries and optimize older ones, and be on call 24/7 for troubleshooting.
One thing to consider is a consulting firm particularly if you are having trouble getting headcount. Even if youre not, though, you can ease into having a DBA, ramping up as needed. For instance, start a consultant on one project, and throw others at him/her as they come up. A full-time DBA might be bored in the first month unless you have a training program for him/her.
So consider a consultant at the very least they can help fill in the gap while you are on your search for a great DBA. I am a big fan of giving back to the community, so consider MySQLs own consulting at http://www.mysql.com/consulting/, or the Pythian Group which publishes the Log Buffer each week, or PalominoDB, which does mostly MySQL remote DBA work (and NoSQL). Or, of course, any of the bloggers on http://www.planetmysql.org that have consulting firms are good choices too.
http://www.google.com/search?q=mysql+consulting
The first place to look for a location-specific full-time DBA is the MySQL User Group near the hiring location:
https://wikis.oracle.com/display/mysql/List+of+MySQL+User+Groups
Contact the leader of the group, saying you have a job opening, and ask if theres an appropriate method to contact the group. Some leaders make the announcements themselves, others allow posting on a message board. If you are an agency, be upfront about it; if youre not, also mention this is for my company, I am not a headhunter or similar language.
Most group leaders are looking to do less work, and the least work possible is to have you come to a meeting and announce your job opening, so any questions can be answered by you right away. If, of course, thats allowed.
Here are my suggestions if youre looking to hire in the Boston area. These are easily translated to looking for folks in your area:
Attend the Boston MySQL User Group and make an announcement. Boston MySQL user group meetings are usually held on the 2nd Monday of every month, but check the calendar to be sure http://mysql.meetup.com/137/calendar/
As I am the leader of the Boston MySQL User Group, I will say that you may also post it to the User Groups message board at http://mysql.meetup.com/137/boards a note of caution, about once a week a job is posted there, so its really better to come to the meeting in person you distinguish yourself. If you cant attend, feel free to send me a description, although I can say its better to go in person, because all I know is what you give me, and if a person has a question youre in a better position to answer it than I am.
Another option is similar groups. I can personally recommend both these groups for high quality people (in general) and you can say that I recommended the groups:
BLU, the Boston Linux and Unix Users group: http://www.blu.org/
and
BBLISA, http://www.bblisa.org/
In all cases, going there in person gives you a lot more cachet to talk about stuff; e-mailing the group leaders asking if you can come and announce your job opening is not a bad thing. (but do stay for the whole presentation; bring your laptop, everyone does, and work on something else if you want, but its polite to stay).
Other pages with lists of user groups that might be helpful:
http://web.meetup.com/cities/us/ma/boston/?from=loc_pick
http://web.mit.edu/ist/usergroups/
(this is a list of all User Groups that MIT hosts, so some are not relevant at all)
I hope this helps!