con estas cabezeras, minimo, deberia de funcionar:
Código PHP:
$headers = 'MIME-Version: 1.0' . "\r\n";
$headers .= 'Content-type: text/html; charset=utf-8' . "\r\n";
Y luego solo le pasas $headers a la funcion mail:
Código PHP:
mail($to, $subject, $message, $headers);