The "direct", although inefficient approach would be to inspect the arrays and look for the values, for example using grep:

for my $key (keys %hash) {
    print "$key\n"
        if grep {$_ eq "banana"} @{ $hash{$key} };
}
[download]

This is inefficient because it searches the entire hash of arrays structure. It would be more efficient if you either structure your data as a hash of hashes from the beginning, or convert it. Then, it's just a matter of hash lookups, which are much faster than grepping an array. Of course, building a second data structure will eat more memory, which could be a problem if the initial data structure is large, but especially for small data structures often the speed gain will outweigh the memory cost.

# convert
my %hoh = map {
        $_ => { map {$_=>1} @{ $hash{$_} } }
    } keys %hash;

# debug: inspect the converted data
use Data::Dumper;
print Dumper(\%hoh);

# lookup
my $search = "banana";
for my $key (keys %hoh) {
    print "$key\n" if $hoh{$key}{$search};
}
[download]

Update: Taking this two steps further, you can build an inverse data structure, so that you don't need to do any searching, you just look up based on the string (banana). This first example applies only (!) if you know that all the values across all of the arrays are unique:

# build inverse hash, if all values are unique
my %inverse_hash;
for my $key (keys %hash) {
    for my $val (@{ $hash{$key} }) {
        $inverse_hash{$val} = $key;
    }
}

# debug: inspect the converted data
print Dumper(\%inverse_hash);

# lookup is simple!
print $inverse_hash{banana}, "\n";
[download]

If there can be duplicate values across the arrays, then an "inverse" hash of arrays would be more appropriate:

# convert to "inverse" hash of arrays (in two steps)
my %hoa;
# first, build a hash of hashes
# (this eliminates duplicates at both levels)
for my $key (keys %hash) {
    for my $val (@{ $hash{$key} }) {
        $hoa{$val}{$key}++;
    }
}
# then, convert the second level of hashes to arrays
for my $vals (values %hoa) {
    $vals = [sort keys %$vals];
}

# debug: inspect the converted data
print Dumper(\%hoa);

# lookup
print join(', ', @{ $hoa{banana} } ), "\n"
[download]

Update 2: In the last example, if you're looking up keys that may not exist, you could use the //[] trick that tybalt89 showed, as in @{ $hoa{banana} // [] }, or you could first check for the existence of the key (e.g. if (exists $hoa{banana})). (Also, in the text above I added a bit of clarification/explanation, e.g. because both the initial data structure and my final example are a hash of arrays.)