Jeśli używasz funkcji mail() w PHP to być może nie masz zainstalowanego sendmail'a, ale z tym rozwiązaniem, maile będą leciały do spamu.
Użyj biblioteki SMTP do PHP i załóż sobie jakąś darmową skrzynkę, np. gmail'a i przez niego przesyłaj maile. Możesz też użyć Amazon SES, jeśli nie wysyłasz więcej niż 62,000 maili miesięcznie, to jest darmowy