An explanation of the code as requested:

## Map the numbers, 0 .. 36 to the symbols we use 
## to represent the number in base37
my @c1 = (' ', '0'..'9', 'A'..'Z' );

sub fromB37 {
    my $n = shift;      ## Get the number to convert
    ## Allocate space for the Base37 representation
    ## Initialise it to the representation of 0 (six spaces)
    my $s = '      ';   
    
    ## For each position in the string
    for( 0 .. 5 ) {
        ## extract the next base37 digit value
        ## look up its representaion character
        ## and assign it to the 'right place' i the string.
        substr( $s, $_, 1 ) = $c1[ $n%37 ] );
        
        ## dividing by 37 effectively right-shifts
        ## the last digit's value out of the number
        $n /= 37;
    }
    $s;
}


my @c2;
## Map the ordinal values of the symbols 
## to their numeric values (0 .. 37)
## The sparse array is faster than a hash    
$c2[  ord( $c1[ $_ ] ) ] = $_ for 0 .. 36;

sub toB37 {
    my $n = 0; ## initialise our return value to 0

    ## split the base37 representation
    ## into a list of the ordinal values of the symbols
    ## and reverse their order to match that produced by fromB37()
    for( reverse unpack 'C*', $_[0] ) {
        ## multiple the running total by 37
        ## (effectively left-shifting the accumulator 
        ## to accommodate the next digit.)
        ## and add value of the next base37 digit
        ## by looking it up in the mapping array
        $n = $n * 37 + $c2[ $_ ];
    }
    ## return the accumulated value.
    $n;
}
[download]

As mbethke points out, these treat the base37 number in 'little-endian' fashion. This because you emphasised compression and speed, with no mention of needing to manipulate the compressed values numerically (sorting).

To get the sortable, big-endian representation, you could use:

my @c1 = (' ', '0'..'9', 'A'..'Z' );
sub fromB37 {
    my $n = shift;
    my $s = '      ';
    substr( $s, $_, 1, $c1[ $n%37 ] ), $n /= 37 for 5, 4, 3, 2, 1, 0;
    $s;
}

my @c2;
$c2[  ord( $c1[ $_ ] ) ] = $_ for 0 .. 36;
sub toB37 {
    my $n = 0;
    $n = $n * 37 + $c2[$_] for unpack 'C*', $_[0];
    $n;
}
[download]

Which actually works out a bit quicker still, but not as fast as mbethke's unrolled version.