I really don't like to have any HTML markup mixed into my Perl code. I highly recommend moving towards something like CGI::Application + HTML::Template. Neither module is core, but both are easily availible on CPAN or through PPM.
Doing it this way for especially complex pages, i can do the initial Mockup in Dreamweaver(yeah yeah i know WYSIWYGs are evil), then simply tweak the template page to my needs. This way your logic and presentation are mostly seperated.
CGI Application has methods for getting at params (I believe it imports CGI.pm's query object.) and It takes care of headers automatically.