Sorting based on values rather than keys suggests you built your hash backwards -- or, if you need both directions, then perhaps you should consider a reverse lookup. BrowserUK suggests an array; another hash would not necessarily be out of the question. It would likely need to be a hash of arrays, however.

my %personInfo = ();
my %stateInfo = ();
while (###) # loop through data
{
    $personInfo{$name} = $state;
    push @{$stateInfo{$state}}, $name;
}
[download]

Now you can look up in either direction.