Firstly, the months in your hash lookup are mixed case, while in your data they're uppercase. Hash keys are case sensitive.

Secondly, in your by_month function you're getting strings like "APR12" and looking them up in a hash with keys like "Apr". You need to strip the number off before looking them up in the hash.

Here's a fixed version of your script:

#!/usr/bin/env perl
my (@months) = qw(APR12 MAR13 APR11 MAR12 FEB13 APR13);

my @mon = map uc, qw( Jan Feb Mar Apr May Jun Jul Aug Sep Oct Nov Dec 
+);
my $mon;
@{$mon}{@mon} = ( 0 .. $#mon );

sub by_month {
    my ($a_mon, $a_yy) = ($a =~ /(...)(..)/);
    my ($b_mon, $b_yy) = ($b =~ /(...)(..)/);
    $mon->{$a_mon} <=> $mon->{$b_mon};
}

@months = ( sort by_month @months );
print "@months\n";
[download]

Note that the above completely ignores the years though. If you want to sort by year first and then month, you could use:

#!/usr/bin/env perl
my (@months) = qw(APR12 MAR13 APR11 MAR12 FEB13 APR13);

my @mon = map uc, qw( Jan Feb Mar Apr May Jun Jul Aug Sep Oct Nov Dec 
+);
my $mon;
@{$mon}{@mon} = ( 0 .. $#mon );

sub by_month {
    my ($a_mon, $a_yy) = ($a =~ /(...)(..)/);
    my ($b_mon, $b_yy) = ($b =~ /(...)(..)/);
    $a_yy <=> $b_yy or $mon->{$a_mon} <=> $mon->{$b_mon};
}

@months = ( sort by_month @months );
print "@months\n";
[download]

If you've got a lot of data, the speed could be improved via a Schwartzian transform, but as you're new to Perl, I won't get into that. ;-)