You are probably aware of the existence of public key certificates. A certificate proves the authenticity of a public key, basically by signing the value of that public key (plus some data on the owner of that key) with a private key of some third party. This third party often is a central Certificate Authority (CA) that is trusted by both the sender and the receiver of the message; in that case, we're talking about a Public Key Infrastructure. An example are the CAs that your web browser trusts: any server certificate signed by these CAs will be trusted by your browser. CAs are also used in (chip) payment cards, identity cards etcetera. (The Web of Trust mentioned above is another option, if there is no central CA that is trusted by both parties.)
So the recipient of the message knows that a message has been signed with the correct private key by means of a 2-step process:
First, validate the certificate belonging to the public key, by means of the public key of the CA that is indicated in the certificate and that is trusted by the recipient.
Then, verify the message itself by checking the signature using the public key in the certificate.
Now finally coming to your question: how does the recipient of the message get to know the public key certificate that allows him to verify the signature over the message? Obviously, the sender of the message should somehow tell the receiver about his identity during the exchange. This can be done by simply sending some identifier as part of the protocol. Next, there are at least three possibilities:
- The recipient already knows the certificate and has stored it
internally. for example because these two parties have been
communicating before.
- The recipient retrieves the certificate from some database.
- The message itself contains the certificate.
What solution is used depends totally on the system. For example, if the communication parties not always online (e.g. for an offline payment terminal), then these parties will always contain their certificates and will exchange these as part of the communication. If all communicating parties in the system are known upfront, it's probably easier to have a central certificate repository.