But Now I Need to get all the "state_name" in above structure into an array.

Well, if you must start from there perhaps Data::DPath is one option.

#!/usr/bin/env perl
use strict;
use warnings;
use Data::DPath 'dpath';

my $foo = {
  '99155' => {
              'PR' => [
                         'state_name=Puerto Rico',
                         'county_names_all=Adjuntas|Utuado',
                       ],
              'AK' => [
                         'state_name=Alaska',
                         'county_names_all=Ketchikan Gateway|Prince of
+ Wales-Hyder',
                       ],
              'WA' => [
                         'state_name=Washington',
                         'county_names_all=Pend Oreille|Spokane|Lincol
+n|Adams',
                         'comments=America/Los_Angeles'
                       ]
            },
  '26134' => {
               'WV' => [
                          'state_name=West Virginia',
                          'county_names_all=Wirt|Wood|Jackson|Ritchie|
+Calhoun',
                          'comments=America/New_York'
                        ]
                 }
};

my @names = map { /=(.*)/ } dpath ('/*/*/*[0]')->match ($foo);
print "@names\n";
[download]

The subsequent filter is left as an exercise.

Update: removed the unnecessary /g modifier. (thanks, LanX)