Yes believe it or not mail does send headers.
You can place header, sessiojn_start, mail, setcookie or any other function that changes the headers anywhere within your script, aslong as there is no output before the use of these functions.
You'll want to add ob_start(); at the top of each PHP page and ob_end_flush(); at the end of each PHP page.
if you have header somewhere other than the top
you need ob_start(); at the top of the page