Embedding fonts in PDFs

To check whether fonts are embedded, use pdffonts, which is included with xpdf. pdffonts gives output that looks like this:

$ pdffonts paper.pdf
name                                 type         emb sub uni object ID
------------------------------------ ------------ --- --- --- ---------
FHQIOS+NimbusRomNo9L-Medi            Type 1       yes yes no       6  0
NEESMN+NimbusRomNo9L-Regu            Type 1       yes yes no       9  0
PJQNOS+CMSY10                        Type 1       yes yes no      12  0

You want "emb" to be "yes" for all fonts (and possibly "sub" as well; also, all fonts should be Type 1, not Type 3). By default in Ubuntu, pdflatex should embed all fonts. Just in case, you can check /etc/texmf/updmap.d/00updmap.cfg, which should have a line like this:

pdftexDownloadBase14 true

If it's set to "false", change it to "true", then run update-updmap as root. Remake the PDF; if it still has non-embedded fonts, your figures are probably to blame. Check your PDF figures and make sure their fonts are embedded (using the pdffonts command). For anything that doesn't have embedded fonts, you can try the following magical invocation (all on one line):

gs -dSAFER -dNOPLATFONTS -dNOPAUSE -dBATCH -sDEVICE=pdfwrite -sPAPERSIZE=letter -dCompatibilityLevel=1.4 -dPDFSETTINGS=/printer -dCompatibilityLevel=1.4 -dMaxSubsetPct=100 -dSubsetFonts=true -dEmbedAllFonts=true -sOutputFile=figures/Mprime-new.pdf -f figures/Mprime.pdf

This creates a file "figures/Mprime-new.pdf" that is hopefully identical to the input file "figures/Mprime.pdf", except that the fonts are embedded. Run pdffonts on it to check.

Once all your figures are in PDF format, remake the paper again. Hopefully, all your fonts are now embedded -- check again with pdffonts.