The latter. For instance, for cgi.parse(), add an explicit deprecation there that says, “See urllib.parse.parse_qs as a replacement.” And I am only thinking about this for cgi since the research was already done as part of the PEP discussion by various folks.
It could also be a whole block at the top, but at least by doing it per feature that has a replacement you will get the suggestion if someone deep-linked into the docs.