1. В какой кодировке php скрипт.
2. В какой кодировке данные приходят в скрипт/какой charset в html странице прописан.
3. В какой кодировке база/таблица/столбец/подключение к базе.
Всё должно быть хотя бы в какой-то одной для начала, и хорошо бы это была UTF-8 (без BOM для текстового редактора).