Have a set of Established Authorities who can grant notary status. They give notary status to people according to their own set of requirements.
The notaries can then add a record on the block chain saying roughly "I do notarization act X on document Y" (It'll be the equivalent of what they enter in their log books today and there will be some corresponding stamp that they'll stamp the physical document with, like they do today). They could now even notarize digital documents by including a hash of the digitized document in their record.
Finally, the agency receiving the notarized document (digital or electronic) can easily go onto the blockchain and verify that the document was indeed notarized as claimed and that the notarization is not a forgery.
Each agency that receives the notarized document could have their own subset of Established Authorities who's notaries they will accept. This means anyone could become an Established Authority, but individual agencies like the US Federal Government could publicly say "hey, our Authority Id is 'USRoxs'" but it'll be up to the receiving agencies like England's government to decide "We trust the system the US uses to validate it's notiaries, so we'll add 'USRoxs' to our list of accepted Established Authorities (along with 'TheEnglish' of course)"