At one place I worked, we found the template idea to be the most flexible way of doing it -- namely because then we could use the same subs for filling out not only HTML but reports written in LaTeX, E-Mail reports, etc.

I myself started out using CGI.pm, then as time went on used less and less of it until I finally just kicked in a sub to parse the parameters and left out the module completely. I guess I'm just obsessive about my HTML :)