I'd just like ro provide some more details on the solution proposed by vartec which is (depending on your MySQL installation) the most correct soultion to your problem.
First of all the character set / encoding issue in MySQL is a somehow complex subject which is extensively covered in the MySQL manual Chapter 9.1 "Character Set Support". In your case especially 9.1.4. "Connection Character Sets and Collations" will be most relevant.
To make it short: MySQL must know which character set / encoding your client application (talking from the database persoective that's your PHP script) is expecting as it'll transcode all the string data from the internal character set / encoding defined at server-, database-, table- or column-level into the connection character set / encoding. You're using UTF-8 on the client side so must tell MySQL that you use UTF-8. This is done by the MySQL command SET NAMES 'utf8'
which must be send as the first query on opening a connection. Depending on your installation and on the MySQL client library you use in the PHP script this can be done automatically on each connect.
If you use PDO it's just a matter of setting a configuration parameter
$db = new PDO($dsn, $user, $password);
$db->setAttribute(PDO::MYSQL_ATTR_INIT_COMMAND, "SET NAMES 'utf8'");
I hope that will help to make the whole thing more understandable.
EDIT:
Using mysqli changing the client character set / encoding is even more simple:
$mysqli = new mysqli("localhost", "user", "password", "db");
$mysqli->set_charset("utf8");