Certificates are typically used to generate confidence in the legitimacy of a public key. Someone verifying a signature can also verify the signer's certificate, to ensure that no forgery or false representation has occurred. These steps can be performed with greater or lesser rigor depending on the context.
The most secure use of authentication involves enclosing one or more certificates with every signed message. The receiver of the message would verify the certificate using the certifying authority's public key and, now confident of the public key of the sender, verify the message's signature. There may be two or more certificates enclosed with the message, forming a hierarchical chain, wherein one certificate testifies to the authenticity of the previous certificate. At the end of a certificate hierarchy is a top-level certifying authority, which is trusted without a certificate from any other certifying authority. The public key of the top-level certifying authority must be independently known, for example, by being widely published.
The more familiar the sender is to the receiver of the message, the less need there is to enclose, and to verify, certificates. If Alice sends messages to Bob every day, Alice can enclose a certificate chain, which Bob verifies on the first day. Bob thereafter stores Alice's public key and no more certificates or certificate verifications are necessary. A sender whose company is known to the receiver may need to enclose only one certificate (issued by the company), whereas a sender whose company is unknown to the receiver may need to enclose two certificates. A good rule of thumb is to enclose just enough of a certificate chain so that the issuer of the highest level certificate in the chain is well-known to the receiver. If there are multiple recipients, then enough certificates should be included to cover what each recipient might need.
In the Public-Key Cryptography Standards (PKCS) (see Question 166), as well as Privacy-Enhanced Mail (PEM) (see Question 130), every signature points to a certificate that validates the public key of the signer. Specifically, each signature contains the name of the issuer of the certificate and the serial number of the certificate. Thus, even if no certificates are enclosed with a message, a verifier can still use the certificate chain to check the status of the public key.