Oy, there's a couple of places to start here...

1) "use strict;" and -w ... once i turned both of those things on, a bunch of little errors became obvious.

2) ARGV refers to your programs args, not your methods args, so you were getting lucky that "new" knew how to open $infile.

3) The difference between $foo and %foo...
This is sometimes a hard thing for people to grasp, but even though you refrence individual valuse of %foo as $foo{bar}, doesn't mean $foo is related.
I think your core problem is that you are never acctually creating the first hash -- even though your print statements make you think you do.
By declaring "my ($States,$other) =({}, {});" you are initializing $States as a hash ref, but when you then refer to "$States{$state}{$city} = $ary;" you aren't doing anything with your hash ref, you are now using the (previously undeclared) global hash %States ...
Your print statements misslead you because they are refering to %States as well!

(BTW: use strict & -w would have pointed those out to you, when I turned them on I got "Global symbol "%States" requires explicit package name at perlmonks.pl line XXX." which is what typed me off.)

take a look at the perlref man page for more info on how to use hash refs.