Проблема частая. Особенно, когда речь идёт о заграничных хостингах. Да что там, даже отечественные хостеры иногда грешат тем, что на их хостинге не работает кодировка UTF-8. Из-за этого все русские буквы отображаются кракозябрами. В статье привожу простой сниппет для вывода необходимых заголовков.
header('Content-Type: text/html; charset=utf-8');
Собственно, это всё. Вместо utf-8 можно так же указать другие кодировки, если это необходимо. А вообще бы по-хорошему, задавать кодировку на уровне сервера. Например, через Charset в Nginx или через AddCharset в Apache.