In some countries, there is a specific legal framework for such things; of course, every country has its own... In France, it is the Référentiel Général de Sécurité, which feeds on Common Criteria. The gist of the thing: the relevant administrative organization (the ANSSI) publishes a Target of Evaluation which describes all the features that a given service should have. This covers things like the precision of the clock of the time stamp authority, the process used to control physical access to servers, the background checks of the criminal and debt records of people who have developed the code, the compliance to relevant standards, and so on.
An organization who wishes to get its system "certified" then hires an independent audit firm, which verifies that the system complies with the rules in the ToE. It then talks to the ANSSI, which does a few verifications itself (in particular that the audit firm is indeed independent and trustworthy), then finally grants a formal recognition of the system as being compliant. This links to a set of local laws which more or less mean that when a certified notary system is used, the notarized documents are presumed valid, and if someone wants to contest their validity, then he has to bring proof elements (i.e. the burden of proof is on who contests rather than on who asserts).
It takes several months, a substantial amount of money (dozens of thousands of dollars), and a terrifying lot of paperwork.