python dictionary match key values in two dictionaries

Use sets to find all equivalents:

for (key, value) in set(aa.items()) & set(bb.items()):
    print '%s: %s is present in both aa and bb' % (key, value)

The & operator here gives you the intersection of both sets; alternatively you could write:

set(aa.items()).intersection(set(bb.items()))

Note that this does create full copies of both dicts so if these are very large you this may not be the best approach.

A shortcut would be to only test the keys:

for key in set(aa) & set(bb):
    if aa[key] == bb[key]:
        print '%s: %s is present in both aa and bb' % (key, value)

Here you only copy the keys of each dict to reduce the memory footprint.

When using Python 2.7, the dict type includes additional methods to create the required sets directly:

for (key, value) in aa.viewitems() & bb.viewitems():
    print '%s: %s is present in both aa and bb' % (key, value)

These are technically dictionary views but for the purposes of this problem they act the same.

This can be written as one-liner with all:

all(bb[k] == v for k, v in aa.iteritems() if k in bb)

It's also more declarative approach, which might convey the intent better.