As a NY attorney and notary myself I feel the need to clarify that an US Notary cannot notarize documents outside of the issuing state's physical boundaries.
A notary public's commission is issued by the individual states and documents may only be notarized WITHIN that commissioning state's jurisdiction. Thus, for example, a NY notary cannot notarize a document in London, UK or in any of the other 49 US states or territories, for that matter. It is why a notarized document generally contains the "STATE OF..., COUNTY OF...," to indicate the physical place in which the document was notarized and to ensure that such location falls within the commissioning state's physical territory.
If you're a NY or CA notary, you cannot notarize documents outside of CA and NY, even if the documents are for use in those jurisdictions.
Documents in the UK need to be notarized at the US embassy by a consular officer, by an authorized US military officer or by a British notary and then apostilled/ legalized at the US embassy.