HTML::Template, because

1. You're going to end up using a template system eventually anyway, and
2. It's easy to use, and
3. Your life is so, so much easier when you do as little HTML in code as you can get away with.

For the HTML I absolutely have to generate by hand, I use a combination of HEREDOCS, CGI.pm methods, and interpolated strings. Whichever is most readable.