The story
Anglo-Norman/Law French, on model of notaire publique, hence the unusual order of adjective following noun, instead of idiomatic English *public notary. Compare attorney general, court martial, fee simple, secretary general, surgeon general.
Etymology from Wiktionary, CC BY-SA 4.0.