Please show your code. (Update: And also take a look at BrowserUk's code. (Update: Oops... Just noticed your post was already a reply to BrowserUk's code post. Well, taking another look would not be wasted effort.))

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]

$ 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]

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