A digital signature is not encryption using a private key, if not just because private key encryption is a contradiction in terms; anybody with a public key can decrypt. It is often explained as encryption with a private key because the RSA signature scheme uses modular exponentiation both for encryption as well as generating signatures. However, even the current RSA standard (PKCS#1 v2.2) goes out of the way to explain that signature generation is not encryption, using different names for the modular exponentiation used for encryption and signature generation. Other signature schemes - such as ECDSA - do not have much in common with encryption directly.
Generally, the public key is distributed and verified through a PKI, a public key infrastructure. Besides being distributed, it is important as well that the public key is trusted. If the public key cannot be trusted, the verifier may accept signatures generated by the wrong private key. For most signature schemes the public keys would always be the same for all verifiers. There are however schemes that only use the public key just once for verification. As it is hard enough to create a well working PKI those schemes are relatively rare though. Commonly PKI is build using certificates, the most well known PKI (PKIX with X.509 certificates) is used for trusted websites in your browser.
For smaller systems you may not need a complex PKI: you could, for instance, calculate a fingerprint over the public key and let the verifier call you to make sure that the fingerprint over the certificate is correct for the key you just send by email.