Depends on your state, depends on your business plan; depends on how you organized (sole prop, LLC, incorporated); depends on how far your business will be expanded.
I would suggest you speak with a CPA for your best business organization options (or an attorney) then speak with an insurance agent about business liability policies.
Most of us self-employed notaries simply go with notary E&O - but not all - some have a very diversified business, being a notary only a part of it so a business liability policy coupled with an E&O policy would be a good combination.