Jeśli używasz mysqli , wydaj to polecenie zaraz po połączeniu:
$mysqli->set_charset("utf8");
Spowoduje to ustawienie kodowania połączenia na UTF8 (takie same, jakich używa Twój stół).
Ze zwykłym mysql , użyj tego:
mysql_query("SET NAMES utf8", $conn);
mysql_query("SET CHARACTER SET utf8", $conn);