Para que funcione la funcion
mail() debes tener un servidor SMTP instalado en tu servidor (valga la redundancia).
Lo más seguro es que no lo tengas. Pero puedes usar la clase
phpmailer que te permite usar un servidor SMTP externo, como
Yahoo,
Hotpot, etc (Servidores de correo que te dan acceso a su servidor smtp). para poder enviar mails. Revisala y nos comentas...
Aquí tienes un artículo excelente que te enseñará a usar esta clase:
http://www.phpfreaks.com/tutorials/130/0.php
Un saludo,