Tienes un servidor smtp instalado? Para que el envío de mensajes usando mail() funcione debe haber un servidor smtp (de correo saliente) instalado y funcionando en el servidor.
Si no lo tienes, puedes intentar usar sockets para abrir una conexión con un servidor smtp externo y enviar mails a través de él.
phpMailer es una librería que entre varias opciones te permite especificar los datos de un servidor externo en caso de que no tengas uno propio. Un ejemplo de servidor externo es una cuenta de orreo electrónico que te brinde acceso a su servidor smtp, como gmail.
