I still can't get it to sort by values. Sorting by keys seems to be easy, but it looks like values were not meant to be sorted by.

No, absolutely not. Sorting by values is OK, as shown by examples above. If you don't get it right, then it means you are simply not doing right.

This is an example built on the code proposed by Kenosis. I have changed and added a couple of names to make sure that the states don't get in the right order just by chance (which was the case with the original data you gave):

use strict;
use warnings;
use Data::Dumper;

my @fname = ( "Philip",  "John", "Daniel", "John",  "Ted" );
my @lname = ( "Johnson", "Hill", "Sharp",  "Evans", "McCain" );
my @state = ( "AK",      "CA",   "AL",     "WI",    "TX");

my %hash = map { $fname[$_] . ' ' . $lname[$_] => $state[$_] } 0 .. $#
+state;
print "Unsorted:\n" ,Dumper \%hash;
print "==========\n";
print "Sorted:\n", map "$_, $hash{$_}\n", sort {$hash{$a} cmp $hash{$b
+}} keys %hash;
[download]

which gives the following output:

$ perl sort_hash.pl
Unsorted:
$VAR1 = {
          'John Evans' => 'WI',
          'Philip Johnson' => 'AK',
          'John Hill' => 'CA',
          'Ted McCain' => 'TX',
          'Daniel Sharp' => 'AL'
        };
==========
Sorted:
Philip Johnson, AK
Daniel Sharp, AL
John Hill, CA
Ted McCain, TX
John Evans, WI
[download]

As you can see, the data is now sorted by the values (i.e. the State).

If you still don't succeed to do it, please show your code.