Add this to your sources.list.

Code:
# Project Aegypten Debs GPG Kmail Plugin #
deb http://ma2geo.mathematik.uni-karlsruhe.de/public-debian binary/
deb http://ma2geo.mathematik.uni-karlsruhe.de/public-debian testing/
deb-src http://ma2geo.mathematik.uni-karlsruhe.de/public-debian binary/
deb-src http://ma2geo.mathematik.uni-karlsruhe.de/public-debian testing/
Then apt-get update and apt-get install newpg libgpgme6 libksba0 cryptplug pinentry-common pinentry-qt should get you everything you need. Then you can go into the Settings -> Configure Kmail -> Security -> Crypto Plugins tab and add the /usr/lib/cryptplug/gpgme-openpgp.so in the location and name it OpenGPG and apply the changes, the warning should now go away and you will get a different message like this when the email is signed.

Code:
Message was signed with unknown key 0x79F1BCE38DE4D38E.
The validity of the signature cannot be verified.
Status: No public key to verify the signature.
This is telling you the plugin works but you have not imported the public key of the person sending the mail into your keyring. If you import the key it looks like this.

Code:
Message was signed by [email protected] (Key ID: 0x79F1BCE38DE4D38E).
The signature is valid, but the key's validity is unknown.
Sign it with your own key and it looks like this and the colour of the message changes to green from yellow.

Code:
Message was signed by [email protected] (Key ID: 0x79F1BCE38DE4D38E).
The signature is valid and the key is fully trusted.
If you want to use GPG signing for your out going messages then you need to create a key with KGpg then edit the file /home/user_name/.gnupg/gpg.conf and uncomment the use-agent line then create a /home/user_name/.gnupg/gpg-agent.conf with the following contents:

Code:
pinentry-program /usr/bin/pinentry-qt
no-grab
default-cache-ttl 1800
Now you edit the /etc/X11/Xsession.d/90newpg_gpg-agent and change to this line at the top of the file.

Code:
STARTGPG=yes
Then you have to return to the Configure Kmail -> Manage Identities and choose the email account for the GPG key you created and select the Modify option, in the Advanced tab of the configuration dialog that pops up use the Change button in the OpenGPG key selection and in the dialog select the key to use then apply the changes. You have to log out of KDE and restart the X server then log back in and every time you send a mail with the account you should have an encryption option to choose too use.