What you want to learn is called the "MySQL Client Server Protocol" - basically, it's the low-level interface with the MySQL server via its defined IP and port number; you connect to it, then use the protocol to communicate with the server. Do a google on "MySQL client server protocol" for some more info; here are a few links to get started:
http://schlueters.de/blog/archives/86-Direct-MySQL-Stream-Access.html
http://forge.mysql.com/wiki/MySQL_Internals_ClientServer_Protocol
Briefly looking at it, though, I am not sure you would be able to do this on a standard Arduino UNO (maybe with a Mega - perhaps with a quadram expander); I should also note that since you are asking this, it might be outside of your skill level. If that is the case, then the simplest method would be to use an intermediate server (PHP or otherwise) that you can send HTTP GET/POST requests and have it interface with the DB.
This isn't a bad solution, just a bit more abstraction, and you're going to likely want some kind of web browser interface to the DB anyhow (likely), so running PHP (or Perl, or whatever) to communicate with the DB isn't a great issue.