Verifica esta referencia del manual de php para la funcion mail():
http://www.php.net/manual/es/function.mail.php
Depende del proveedor quizas necesites enviar el correo por SMTP que el proveedor de hosting te puede brindar. Aqui hay un post interesante que explica como enviar correos utilizando SMTP y PHP:
http://www.9lessons.info/2009/10/sen...p-and-php.html