1. Reduce all variable and subroutine names down to single characters. Eliminate as much whitespace as possible. These might be obvious, but it's certainly a starting point. For purposes of readability of this tutorial, whitespace is NOT fully eliminated. And thanks to a reminder from liverpole, the return value of a subroutine is the last statement of the subroutine, so all those pesky returns should be able to be dropped as well.
2. Do you really need strict compliance? Get rid of variable declarations where possible. Dropping this:

   my(%s,$y,$l,$t,$d);
   [download]

   turns something like this:

   my $k = k(\%s);
   [download]

   into this:

   $k = k();
   [download]

   Limbic~Region reminds me that:

   $k=&k;
   [download]

   ... is still shorter, and if sub k is defined before it's called, it can be shorter still:

   $k=k;
   [download]

   and this:

   my $l = $d / int(length($t) / $k) / 100;
   [download]

   into this:

   $l = $d / int(length($t) / $k) / 100;
   [download]

   liverpole suggests that clever rearrangement of operands yields a few more savings:

   $l = $d / 100 / int length($t)/ $k;
   [download]

   Also, any numerical value assigned to $* is implicitly an int, and whio suggests that y///c is a character short than length, so now we have:

   $* = $d / $t=~y///c / $k;
   [download]

   Note: Yes, I did drop dividing by 100. My original code wouldn't work without it, my new golfed code won't work with it. I don't know the exact change that removed its necessity.
   More hints: $_ doesn't need to be declared as a my variable. $* removes the necessity for converting a value to an int, and whio suggests further that $- and $= have similar behavior, except $- can't be negative.
3. Do you actually need lexically scoped variables? If you do, take as much advantage of any "my" declarations as you can:

   sub i{
     my ($g,$l,$t) = @_;
     my @c;
     ...
   }
   [download]

   1. $l and $t are now globals, so those get dropped, but I still need a lexically scoped $g. Also, the code calling this sub is shortened to also take advantage of the globals.
   2. I still need a lexically scoped array @c, and I know that sub i will never be called with more than one parameter, so I save some characters:

   sub i{
     my ($g,@c) = @_;
     ...
   }
   [download]

4. my($o)=@_; is 1 less character than my$o=shift;. Furthermore, if you know that subroutine will always get called with a valid parameter, you can save even more: ($o)=@_;. liverpole points out that $o=pop; is shorter still.
5. Rearrange while and for loops in postfix notation where possible (one statement per iteration), as I've demonstrated and whio explicitly state, the postfix notation removes the need for the parens and braces, and while's are generally spelled better as for:

   for(3..6){u($_)}
   [download]

   becomes:

   u($_)for 3..6;
   [download]

6. Taking advantage of default expressions for functions (generally $_), remembering other defaults for operators and other perl idioms (<>, for example), along with the above hint turns this:

   while(<STDIN>){$t.=lc$_}
   [download]

   into this:

   $t.=lc for<>;
   [download]

   If you need to rotate an array, try it in a subroutine so you can take advantage of @_:

   push @_, shift;
   [download]

   If it's an array of arrays that you want to rotate:

   push@$_, shift@$_ for @AoA;
   [download]

7. 'Inline' subroutine and function calls. Dropping a global $k out of the call and dropping "my" where it isn't necessary turn this:

   my $n = t($_,$k);
   my %n = f($n);
   [download]

   into:

   %n = f(t($_));
   [download]

   Define sub t and sub f ahead of time, and you're left with:

   %n = f t$_;
   [download]

8. When you can't postfix a for loop, try to use map in void context. This, combined with dropping globals, dropping lexical scoping, and adding inline functions, defining sub t, sub b, and sub i ahead of time (along with rearranging the inputs to sub b takes something like this:

   for(0..($k-1)){
     my $n = t($_,$k);
     my %n = f($n);
     my @g = b(1,\%n);
     $y   .= i(\@g,$l,\%t)
   }
   [download]

   and turns it into this:

   map{
     %n = f t$_;
     @g = b\%n,1;
     $y .= i\@g
   } 0..$k-1;
   [download]

9. Drop temporary variables where possible. Cast function/subroutine return types. Combining this idea with inline functions in a simple example:

   @array = routine1($param1,$param2);
   $result = join ':', @array;
   [download]

   becomes:

   $result = join ':', @{routine1($param1,$param2)}
   [download]

   Combining this idea with using map in a void context, inline functions, taking two suggestions from whio to eliminate an extra character in a comparison (turning >= into <), and the reminder that $x =~ /./g is shorter than split //, $x, and rearranging a few operands takes this code:

   for((split//,$t)){
     my $l = (split //,$y)[$c];
     my $s = join '', @$l;
     my $p = index($s,$_);
     $o   .= $p >= 0 ? $a[$p] : $_;
     $c   += $c < $k-1 ? 1 : -$k+1
   }
   [download]

   and turns it into:

   map{
     $p  = index((join '', @{($y=~/./g)[$c]} ), $_);
     $o .= $p < 0 ? $_ : $a[$p];
     $c += $c < $k-1 ? 1 : 1-$k
   } $t =~ /./gs;
   [download]

10. Drop "if" checks when iterating when possible. Don't forget the ||= operator. Combining this with postfix for loop notation:

    for(a..z){
      if( ! $d{$_} ){
        $d{$_} = 0
      }
    }
    [download]

    becomes:

    # no, you don't need a space between the 0 and the for.
    $d{$_} ||= 0for a..z;
    [download]

11. Remember how your data is used. In the original fuller version, I was formatting the return value for display. In my golfed version, I no longer display intermediary values, so I can drop the formatting:

    my @k = map { $_->[1] } sort { $b->[0] <=> $a->[0] } @c;
    my $r = $k[0];
    $r =~ s/([a-z])\s\(.*/$1/;
    return $r
    [download]

    with dropping the intermediary variable @k, becomes:

    return( map{ $_->[1] } sort { $b->[0] <=> $a->[0] } @c )[0]
    [download]

More examples:

1. Taking advantage of subroutine parameter initialization to get extra lexical variables, postfix for notation, new globals, dropping return:

   sub b{
     my( $e, $l ) = @_;
     my @g;
     for(sort keys %$l){
       push @g, [ $_, '=', (split //,'#' x int($$l{$_} * $e))]
     }
     return @g
   }
   [download]

   becomes:

   sub b {
     my( $e, $l, @g) = @_;
     push @g, [ $_, (split //,'#' x int($$l{$_} * $e))] for sort keys %$l
   +;
     @g
   }
   [download]

2. Populating a hash with a default values for all desired keys if the array passed in doesn't already contain them:

   sub f{
     my %d;
     $d{$_}++ for grep /[a-z]/, split //, shift;
     for(a..z){
       if( ! $d{$_}){
         $d{$_} = 0
       }
     }
     return %d
   }
   [download]

   becomes:

   sub f{
     my %d;
     $d{$_}++for grep /[a-z]/, shift=~/./g;
     $d{$_} ||= 0for a..z;
     %d
   }
   [download]

3. Using globals, taking advantage of subroutine parameter initialization, using map in void context instead of a for loop (twice), dropping temporary variables, ignoring display formatting, dropping return:

   sub i{
     my ($g,$l,$t) = @_;
     my @c;
     for(0..25){
       my $v = v($g,$l,$t);
       push @c, o($v,$$g[0][0]);
       w($g)
     }
     my @k = map{ $_->[1] }
            sort{ $b->[0]<=>$a->[0] } @c;
     my $r = $k[0];
     $r =~ s/([a-z])\s\(.*/$1/;
     return $r
   }
   [download]

   becomes:

   sub i{
     my ($g,@c) = @_;
     map{ push @c, o(v($g), $$g[0][0]); w($g) } 0..25;
     ( map{ $_->[1] } sort { $b->[0] <=> $a->[0] } @c )[0]
   }
   [download]

4. Using a global (instead of passing a hashref), inlining functions, defining subroutines ahead of time:

   sub k{
     my $s = shift;
     my @g;
     for( sort{ $$s{$b} <=> $$s{$a} || $a cmp $b } keys %$s ){
       last if $$s{$_} < 3;
       next unless $_ =~ y/a-z// > 2;
       my @f;
       push @f, ( pos($t)-3 ) while $t =~ /$_/g;
       my $g = c(n(@f));
       $g > 2 && push @g, $g
     }
     return c(@g)
   }
   [download]

   becomes:

   sub k{
     my @g;
     for( sort{ $s{$b} <=> $s{$a} } keys %s ){
       last if $s{$_} < 3;
       next unless y/a-z// > 2;
       my @f;
       push @f, (pos($t)-3) while $t =~ /$_/g;
       my $g = c n@f;
       $g > 2 && push @g, $g
     }
     c@g
   }
   [download]

5. Rolling two for loops into maps shaved a few characters, and I let perl auto-vivify $c as a numeric scalar in context:

   sub o{
     my ($g,$w) = @_;
     my $c = 0;
     for( @$g ){
       for( @$_ ){
         /\+/ && $c++;
         /\-/ && $c--
       }
     }
     return [$c,$w]
   }
   [download]

   becomes:

   sub o{
     my ($g,$w,$c) = @_;
     map{
       map{ /\+/ && $c++; /\-/ && $c--} @$_
     } @$g;
     [$c,$w]
   }
   [download]

6. Using a global, rolling a for loop into a map, convert split's to /./g:

   sub t{
     my ($o,$k) = @_;
     my $c = 0;
     my $r;
     for(split //,$t){
       $r .= $_ unless(($c+($k-$o)) % $k);
       $c++
     }
     $r =~ s/[^a-z]//g;
     return $r
   }
   [download]

   becomes:

   sub t{
     my ($o) = @_;
     my $c = 0;
     my $r;
     map{ $r .= $_ unless($k-$o+$c) % $k; $c++ } $t=~/./gs;
     $r =~ s/[^a-z]//g;
     $r
   }
   [download]

7. Using globals, skipping a my declaration (I know the sub only be called with a single, valid parameter, so $s will always be unique), rolling two for loops in maps in void context, skipping a long if(){}elsif(){} by using the ternary ?: with the same net effect, defining subs ahead of time:

   sub v {
     my ($m,$l,$t) = @_;
     my @g = b($l,$t);
     my $s = \@g;
     my $z = 0;
     for( @$m ){
       my $x = 0;
       for( @$_ ){
         if( $$m[$z][$x] eq '#' && $$s[$z][$x] eq '#' ){
           $$s[$z][$x] = '+'
         }
         elsif( $$m[$z][$x] eq '#'&&$$s[$z][$x] ne '#' ){
           $$s[$z][$x] = '-'
         }
         $x++
       }
       $z++
     }
     return $s
   }
   [download]

   becomes:

   sub v{
     $m = pop;
     my @g = b\%t,$*;
     $s = \@g;
     $z = 0;
     map{ $x=0;
          map{
              $$s[$z][$x] = $$m[$z][$x] eq '#' && $$s[$z][$x] eq '#' ? '+
   +' : '-';
              $x++
             } @$_;
          $z++
        } @$m;
     $s
   }
   [download]