I would be inclined to alter the data structure and end up with something like this:

#!/usr/bin/perl
use strict;
use warnings;

my %data = (
    'Washington' => {
               'car'   => 'Honda',
               'names' => ['Eric','Smith']
    },
    'California' => {
               'car'   => 'BMW',
               'names' => ['John','Paddy','Josh']
    }
);

for my $state (sort keys %data) {
    my $car = $data{$state}{car};
    for my $name ( @{ $data{$state}{names} } ) {
        $state .= ":" if $state ne '';
        printf "%12s %s drives %s\n", $state, $name, $car;
        $state = '';
    }
}
[download]

Cheers,
R.