You should try seeing what CGI does:

 perl -MCGI -e 'my $q = CGI->new(); print $q->header(-type=>"text/html
+", cookie => $q->cookie(-name=>"foo",-value=>"bar"))'
[download]

This prints the "Set-Cookie" line first, and follows the "Content-Type" with the required double-newline