am I missing something? why would you assume it's included by default in Ubuntu?

Right: you need to compile it first. And then copy xpdf/pdftojson to your binary path like /usr/local/bin/pdftojson so that it is found

I think you forgot the configure/make dance?