In general, if you want to group things for lookup, you're talking about a hash. If you want things in order, you're talking about an array.

In this case, as with many real world problems, you sort of want a little of both - you want a hash of arrays.

At the top level, you want a hash keyed off of state. The value for each of these, you want a list of address information for that state - an array of addresses. Then, your printout loop looks kind of like:

foreach my $state (keys %addresses) {
   foreach my $address (@{$addresses{$state}}) {
      write $filehandle($state) $address . "\n";
   }
}
[download]

(Obviously leaving out some steps, like creating your filehandles and building up the data structure. But see how simple that organization makes it to deal with?)