LaTeX uses the \everypar token register to set up the error. If you try \showthe\everypar before \begin{document} you will see
> \@nodocument .
l.3 \showthe\everypar
The internal command \@nodocument expands to give the error. This works as TeX inserts \everypar each time it starts a paragraph, and that happens when it encounters horizontal mode material while in vertical mode. TeX starts off in vertical mode, and the first letter or similar causes a switch to horizontal mode, inserts \everypar and thus here fires the error.
Part of the \document macro removes \@nodocument from \everypar. So you want to add something to it, and remove or disable it again as part of \maketitle. You also need to activate that in the right place, at the end of \document. Something like
\makeatletter
\g@addto@macro{\document}{\everypar\expandafter{\the\everypar\my@title@check}}
\g@addto@macro{\maketitle}{\global\let\my@title@check\relax}
\newcommand*{\my@title@check}{\PackageError{MyPkg}{Missing \protect\maketitle}\@ehc}
\makeatother
Rather than remove the check from \everypar, I've taken the route of simply converting it to a no-op once \maketitle has been used. You could also use a flag, for example if you have further tests to do. (Removing from the toks would require a bit of care for the general case, so I'm avoiding the issue.)