Let's say that I sign someone's key and then later decide that was a bad idea - either it was a bad idea at all, or I should have signed it with a different level of trust. Is it possible, both in a theoretical and also in a practical way, to "un-sign" someone else's key?
Removing a Local-Only Signature
If the signature is still only kept locally (either by never sending it to anybody or the key servers, or by even having performed an
lsign which creates signatures that cannot be uploaded), you can actually delete it by running
gpg --edit-key [keyid] [select a uid] delsig [go through the assistant for deleting signatures] save
Revoking Published Signatures
If a signature was already sent to the key servers, you still can delete it locally, but you will not be able to remove anything from the key servers. The OpenPGP key server infrastructure is designed not to delete/forget anything, to be resistant against deletion attacks (where the attacker wants to remove eg. your key).
Instead of deleting the signature, now revoke it. This time, run
gpg --edit-key [keyid] revsig [go through the assistant for revoking signatures] save
Now you should upload the revocation certificate (which more or less states "This certificate invalidates the signature I made starting from a given date for the reason given") to the key servers by running
gpg --send-key [key-id].
As soon as the revocation sync'd throughout the key servers (some minutes) and other users will update key
[keyid] (unknown time, possibly rather long), the revoked signature will not be taken into account any more when calculating validity and be displayed as revoked when listing the signatures.
You can't unsign, but you can revoke your signature on their key. Once someone has synced both the original signature and the revocation, their UI should show both and will no longer use the signature in trust calculations. To do this with GnuPG:
gpg --edit-key KEYID revsig <Supply a reason> gpg --send-key KEYID # Upload key to keyserver, or gpg --armor --export KEYID # Manual upload to keyserver