Discrete legend

I am plotting a number of polygons with different colours (results
from an image clustering or classification algorithm). I'd like to
have a map-like legend, with a square filled with some colour and some
text describing what it is (a quick search in Google comes up with the
following example:
<https://secure.cityofno.com/Resources/Portal50/map_key.jpg>. Scary,
though hopefully you get the gist of it :D).

I realise that the legend class has some support for patches, but how
does one go about using them? I can't just add a legend (I get a very
messy legend, one for every patch in my plot). I should be able to set
my legend somewhere, but I don't know where to start: pylab.legend?

Any hints or examples greatly appreciated!