Finally figured it out. Had to place it in the -head option:

use CGI qw/:standard/;

print header,
start_html
(
-dtd => '-//W3C//DTD XHTML 1.0 Strict//EN" "http://www.w3.org/TR/xhtml
+1/DTD/xhtml1-strict.dtd',
-title => "Test",
-head => script({-type => 'text/javascript', -src=>'../test.js'})
),
"Test",
end_html;
[download]