How does GPG verify succesful decryption?
This is hidden well in RFC 4880, the OpenPGP message format specification.

Section 5.7 explains how message data is encrypted. (I'm using the values for a 16-byte block cipher like AES.)


A random block of data is created: $p_{1} \dots p_{16}$
The last two bytes of this block are repeated: $(p_{17}, p_{18}) := (p_{15}, p_{16})$.


These 18 bytes (in case of AES or another similar block cipher) are encrypted in CFB mode (with a zero initialization vector), i.e. $(c_{1} \dots c_{16}) = E_K(0, \dots 0) \oplus (p_{1} \dots p_{16})$, and $(c_{17}, c_{18}) = \text{first 2 bytes of}(E_K(c_{1} \dots c_{16})) \oplus (p_{17}, p_{18})$.

When decrypting, we just have to decrypt these 18 bytes $c_1 \dots c_{18}$ (i.e. we calculate $p_1 \dots p_{16} = E_K(0) \oplus (c_{1} \dots c_{16})$, $(p_{17}, p_{18}) = \text{first 2 bytes of}(E_K(c_{1} \dots c_{16})) \oplus (c_{17}, c_{18})$) and check $p_{15} = p_{17}$ and $p_{16} = p_{18}$. If these are not the same, we throw the "bad key" error message.

Of course, this is only a heuristic check: One in each $2^{16}$ keys will still look right.

If you need a more certain check of the right key, use either a digital signature (in the encrypted package), or use a "Symmetrically Encrypted Integrity Protected Data Packet" (section 5.13) instead of a plain encrypted packet.