It does send the header, before header() even returns. Your code should be:

#!/usr/local/bin/perl
use CGI;
use CGI::Carp qw(fatalsToBrowser);
use strict;
my $query = new CGI;
my $cookie = $query->cookie(
    -name    => 'test',
    -value   => 'banana'
);

print $query->header(-type => "text/html", -cookie => $cookie );

print "Hello";
[download]

under mod_perl (and if not an NPH script), that's the same as:

#!/usr/local/bin/perl
use CGI;
use CGI::Carp qw(fatalsToBrowser);
use strict;
my $query = new CGI;
my $cookie = $query->cookie(
    -name    => 'test',
    -value   => 'banana'
);

$query->header(-type => "text/html", -cookie => $cookie );

print "Hello";
[download]

which DOES send the header. Look at the source of CGI.pm