TMI — Too Much Information. You're actually sorting by the values of the keys (i.e., the state codes) and not by the keys (the cities).

c:\@Work\Perl\monks>perl -wMstrict -MData::Dumper -le
"my %cities = (
      Tucson  => 'AZ',
      Boston  => 'MA',
      Jackson => 'MS',
      Dixon   => 'NM',
      Denton  => 'TX',
      Cincinnati   => 'OH',
  );
      print Dumper(\%cities);
  foreach my $place (sort keys %cities) {
      my $state = $cities{$place} ;
      print \"$place, $state \n\";
  }
"
$VAR1 = {
          'Cincinnati' => 'OH',
          'Tucson' => 'AZ',
          'Dixon' => 'NM',
          'Jackson' => 'MS',
          'Denton' => 'TX',
          'Boston' => 'MA'
        };

Boston, MA

Cincinnati, OH

Denton, TX

Dixon, NM

Jackson, MS

Tucson, AZ
[download]

Update 1: I was going to add some example code to handle the numbering, but BrowserUk beat me to it.

Update 2: This might give you a better idea of what's going on in your original sort block:

c:\@Work\Perl\monks>perl -wMstrict -e
"my %cities = qw(
   Tucson AZ  Boston MA  Jackson MS  Dixon NM  Denton TX  Cincinnati O
+H
   );
 for my $place (sort { printf qq{'$cities{$a}' };   $cities{$a} cmp $c
+ities{$b}; } keys %cities) {
   print qq{\n '$place' in '$cities{$place}'};
   }
"
'OH' 'NM' 'TX' 'AZ' 'MS' 'OH' 'AZ' 'MA' 'MS' 'TX' 'TX'
 'Tucson' in 'AZ'
 'Boston' in 'MA'
 'Jackson' in 'MS'
 'Dixon' in 'NM'
 'Cincinnati' in 'OH'
 'Denton' in 'TX'
[download]