NOTE: The following assumes both keys and value have to match. If you just want to check for value matches, there are a couple different ways you could go about it, depending on whether all values in each hash are unique or not, and if not, whether you want all matches listed or just the first.

use strict;
use warnings;

my ($k1, $k2, %foo, %bar);

%foo = (
         'a' => {
                  'x' => 1,
                  'y' => 3
                },
         'b' => {
                  'x' => 4,
                  'y' => 4
                }
       );
%bar = (
         'a' => {
                  'x' => 1,
                  'y' => 2
                },
         'b' => {
                  'x' => 3,
                  'y' => 4
                }
       );
for $k1 (sort keys %foo) {
    for $k2 (sort keys %{$foo{$k1}}) {
        print "\$foo{$k1}{$k2} eq \$bar{$k1}{$k2} with value $foo{$k1}
+{$k2}\n"
            if $foo{$k1}{$k2} eq $bar{$k1}{$k2};
    }
}
[download]

EDIT: Here's some code to report all value matches:

use strict;
use warnings;
use Data::Dumper;

my ($k1, $k2, %foo, %bar, %fval, %bval);

%foo = (
         'a' => {
                  'x' => 1,
                  'y' => 3
                },
         'b' => {
                  'x' => 4,
                  'y' => 4
                }
       );
%bar = (
         'a' => {
                  'x' => 1,
                  'y' => 2
                },
         'b' => {
                  'x' => 3,
                  'y' => 4
                }
       );
for $k1 (keys %foo) {
    for $k2 (keys %{$foo{$k1}}) {
        push @{$fval{$foo{$k1}{$k2}}}, "$k1\t$k2";
    }
}
for $k1 (keys %bar) {
    for $k2 (keys %{$bar{$k1}}) {
        push @{$bval{$bar{$k1}{$k2}}}, "$k1\t$k2";
    }
}
for $k1 (sort keys %fval) {
    if (exists $bval{$k1}) {
        print "Value $k1 matches for:\n";
        for (sort @{$fval{$k1}}) {
             @_ = split /\t/;
             print "    \$foo{$_[0]}{$_[1]}\n";
        }
        for (sort @{$bval{$k1}}) {
             @_ = split /\t/;
             print "    \$bar{$_[0]}{$_[1]}\n";
        }
        print "\n";
    }
}
[download]