A função header() serve apra enviar ao servidor web uma modificação do cabeçalho HTTP, por isso se você utilizar qualquer função que exiba caracteres na tela (como o echo ou printf) antes do Header, ele dará esse erro.
A melhor opção é você utilizar a classe PHPMailer, ao invés do mail(), Não precisa instalar nada, basta adicionar a classe ao seu arquivo de envio de e-mail. Veja o tutorial nesse link: http://blog.thiagobelem.net/php/enviar-e-m...do-o-phpmailer/