First read the question What is a digital signature? You’ll then understand what the problem is with those signatures. You can’t really proof that the public key that the sender owns to decrypt the message actually belongs to you. That’s where a digital certificate comes in. Those certificates are issued by a certificate authority (CA) which you would have to pay and give lots of information about your identity. You’d also have to send them your public key. The CA uses all this information to generate a certificate and send it back to you. The standard for digital certificates is X.509. It contains information about your identity, your public key and things like a validity period, etc. It’s important that you choose a well-known CA that other people will trust. The CA will have encrypted the certificate with their private key.
When party A now sends a message to party B, it will sign the message with his certificate. Party B will ensure this certificate is correct by decrypting it using the CA’s public key. Now party B has access to your public key and can decrypt the signature to verify the authentication.
BTW, you can also generate a certificate yourself (eg. using the tool keytool) and use that. But people are not likely to accept that certificate as there is no trusted third party involved.
The standard for digital certificates is X.509. This standard allows for certificate chaining. This allows certificates to be put in a hierarchy. Maybe party B doesn’t trust the first CA, but goes up in the hierarchy and finds one that he trusts. For example, an employee of a company might get a certificate from his company who is in turned signed by Thawte (the root CA). Now suppose that employee uses his certificate to try to get the receiver trust him. The receiver isn’t eager to trust the one that issued the certificate, but since that certificate is signed in turn by Thawte, he trust the original certificate.