Cache::File
http://search.cpan.org/~cleishman/Cache-2.04/lib/Cache/File.pm
↑これ
http://search.cpan.org/~bbb/File-NFSLock-1.20/lib/File/NFSLock.pm
http://search.cpan.org/~gbarr/TimeDate-1.16/lib/Date/Parse.pm
http://search.cpan.org/~gbarr/TimeDate-1.16/lib/Time/Zone.pm
↑依存モジュール

で、普通に動いたんですけど・・
あんまり軽くなってないorz
ボトルネックどこだ・・。
HDDが遅いんかな？ｗ

↓以下ソース。
※Cache::File とか Template::Toolkitのサンプルと思ってください。。
特に新しいことはやってません。

#!/usr/bin/perl
use strict;
use warnings;

use lib '/home/hogehoge/modules';#モジュール置いた場所
use Hoge; #DBアクセス系
use Template;
use CGI;
use Cache::File;
my $cache_path = '/home/hogehoge/tmp/cache'; #キャッシュパス
my $q = new CGI;

#パラメータがなかったらリダイレクト
unless($q->param('tag')){
    print "Location: http://hogehoge.hoge\n\n";
}
my $cache = Cache::File->new(cache_root => $cache_path) or die 'Cache::File->new';
my $cache_key = 'key_' . $q->param('tag');

# キャッシュを取得
my $html = $cache->get($cache_key);
unless($html){
    my $conf = {
        INCLUDE_PATH => './tt2',
    };
    my $t = Template->new($conf);
    my $tt2 = 'tag.tt2';
    my ($rows);
    if($q->param('tag')){
        # ここ該当するタグが含まれる一覧取得するとこ
        my $dbh = Hoge::DBConnect(); #DBコネクション
        $rows = Hoge::Get_files($dbh,$q);
    }

    my $vars = {
        'q' => $q,
        'rows' => $rows,
    };
    $t->process(
        $tt2,
        $vars,
        \$html,
    ) || die $t->error();

    # ここでキャッシュをセット
    $cache->set($cache_key, $html, '1 weeks');
}
print "Content-type:text/html\n\n";
print $html;
__END__

補足:
最後のprintは、手抜きです。
ちゃんとやるなら・・headerとfooterは、CGI.pmで出力するのがよろしいかと。
キャッシュは1週間にしたけど・・長すぎかな・・。