The notarial form should state whether the notary knows the witnesses or whether they have probided ID (generally a driver license with photo). The witnesses do not need to know the person signing the Will or codicil - and that is generally best. It is a bad idea to have a beneficiary as a witness. Persons that you know - so long as they are not beneficiaries - can be witnesses to a Will or Codicil.
They can be strangers, but they have to be competent adults, able to determine generally that you are of sound mind yourself (the formalities for a codicil are the same as for a will).
This is not legal advice nor intended to create an attorney-client relationship. The information provided here is informational in nature only. This attorney may not be licensed in the jurisdiction which you have a question about so the answer could be only general in nature. Visit Steve Zelinger's website: http://www.stevenzelinger.com/
The witnesses can be total strangers. Make sure their correct addresses are on the will so they can be located if necessary after you pass. Make sure their names are clear. If they are strangers to you, they will be strangers to your family and your personal representative. If they need to be tracked down because there is a question regarding execution of your Will, you want to make it easy on everyone.
The general advice above does not constitute an attorney-client relationship: you haven't hired me or my firm or given me confidential information by posting on this public forum, and my answer on this public forum does not constitute attorney-client advice. IRS Circular 230 Disclosure: In order to comply with requirements imposed by the Internal Revenue Service, we inform you that any U.S. tax advice contained in this communication (including any attachments) is not intended to be used, and cannot be used, for the purpose of (i) avoiding penalties under the Internal Revenue Code or (ii) promoting, marketing, or recommending to another party any transaction or matter addressed herein.