Here's another, similar, approach...

#!/usr/bin/perl -w
use strict;

# put data in an array (however you want to do it)
my @weather_data = split "\n", <<_END_;
Ca,Freemont 87 45 91 56 89 54 67 45 76 43 81 48 76 43
Ca,Berkley 56 34 67 38 66 34 56 31 67 45 71 45 65 42
Tx,Houston 88 34 77 36 75 31 72 30 81 31 79 51 75 28
Tx,Dallas 76 43 79 45 87 28 86 32 84 45 78 46 83 23
_END_

# store data here
my %temp = ();

# cycle through all data
for (@weather_data) {

  # grab state and city
  next unless (/^(\w+)\W+(\w+)/);
  my $state=$1;
  my $city=$2;

  # set as default if none set
  $temp{$state}{'max_city'} ||= $city;
  $temp{$state}{'min_city'} ||= $city;

  # grab and compare temperatures 
  while (s/(\d+)//) {
    my $this_temp = $1;

    # set as max/min if none set
    $temp{$state}{'max'} ||= $this_temp;
    $temp{$state}{'min'} ||= $this_temp;

    # check whether temp new max or min and assign data
    if ($temp{$state}{'max'} < $this_temp) {
      $temp{$state}{'max_city'} = $city; 
      $temp{$state}{'max'}      = $this_temp;
    }
    elsif ($temp{$state}{'min'} > $this_temp) {
      $temp{$state}{'min_city'} = $city;
      $temp{$state}{'min'} = $this_temp;
    }
  }
}
# display results
for (keys %temp) {
  print "$_ max temp $temp{$_}{'max'} $temp{$_}{'max_city'}\n";
  print "   min temp $temp{$_}{'min'} $temp{$_}{'min_city'}\n\n";
}
[download]

Of course, you'll have to amend this if you want all results shown in the case of a tie :)

cLive ;-)