This means something was already outputted by your script before your header() command. You need to either:
Look for blank space before and after the "<?PHP" "?>" tags.
OR
Look for any echo, print, etc. commands that output data before the header() is called. Either remove them or read about output buffering ([man]ob_start[/man]).
EDIT: If you can't solve it on your own, post the entire code of formmail.php EXACTLY as it is (Cntrl+A, Copy, for example). If it is a very large script (say... 25+ lines) don't paste it as code; instead, attach the script to your post.