What version of CGI.pm are you using? Last I heard the more recent versions print out valid XHTML (I prefer templating systems and don't use it to print HTML often, so I could be mistaken).

You also have to do a print $q->header('text/html'); or the like to print a header. See the docs for more detail.