To simplify on the above solutions...
You can use the closure method, but that is really making a new sort function for each hash you have.
What you want is a function that takes a hash, and returns the sorted keys.

sub sorted_by_dept(\%) {
  my $href = shift;
  my @sorted =  map {$_->[0] }
                sort {$a->[1] <=> $b->[1] }
                map { [$_, $href->{$_}->{dept}] }
                keys %$href;
  return @sorted;
}
[download]

To break this down, follow it backwards. Starting at keys -- for each key in the hash, the last map builds pairs of values. The first number of the pair is the end value you want. The second number of the pair is what you want to sort by.
The sort command sorts by the second number, and the upper map looks up the original key value for you.
You then have a sorted list of keys you can use in a foreach.

Hope this helps,
~jmanning2k