matplotlib.rcParams['ps.useafm'] = True
matplotlib.rcParams['pdf.use14corefonts'] = True
matplotlib.rcParams['text.usetex'] = True
Finding those 3 lines somehow wasn't that trivial - I would've expected this to come up more often. Maybe my google-foo is no good here.
Update: as someone helpfully pointed out, the matplotlibrc is a more elegant way to accomplish this feat. The lines above can be added to the file, so you don't have to edit every one of the scripts (or digging for these lines around your code or the intertubes ever again).