I would also recommend HTML::Template. To add a bit more check out some framework for CGI applications. Such as CGI::Application.
HTML::Template + CGI::Application work well together - and there are many resources about both (CGI::App even has it's own Wiki with tutorials, articles FAQ ...etc)
It wont get you too far away from "dirty Perl" - but it's a much better and cleaner approach. Not to mention it's much faster way to write code ... Actually I'm running whole web sites on it - and even under plain CGI it works reasonably well.
Template toolkit might be another good option - but somehow I got the same feeling - it's simply not it. It's not Perl, it's not HTML. Maybe I'm wrong (probably I am since many people say it's good) as I still haven't had time to read book about it ...