cookie у вас не "не сохраняются", а не отправляются.
потому, что кроме заголовков, что то уже отправлено клиенту.
самая распространенная (и для новичков, самая загадочная) причина в том, что
в PHP, все, что не в
<? ... ?>
выводится в браузер. например:
<?PHP
echo 'Это PHP код';
?>
а это не PHP код, и в браузер будет выведено как простой текст, даже если это просто пробел или символ перевода строки.
таким образом, для контроля за выводом, надо контролировать либо все (абсолютно все) символы после тега
?>
либо вообще не использовать закрывающий тег, что в комментариях выше, правильно посоветовал
@maxaon
кстати, NetBeans в последней версии (7.4) тоже рекомендует убирать закрывающий тег.