I don't know anything about HTML::Template with utf8, but as for mysql:

Make sure you've got the latest DBD::MySQL (or at least 4.004). Use the mysql_enable_utf8 option. Make sure all your utf8 columns really have an utf8 type.

Use place holders/bind vars and make sure all text inserted on utf8 columns really is utf8. You can use utf8::upgrade for that.

Selects should work out of the box for text and binary.