My blog post (the passingcuriosity.com link in John Boker's answer) does AES -- a symmetric encryption algorithm -- using the M2Crypto library. M2Crypto is a Python wrapper around OpenSSL. The API is pretty much a straight translation of OpenSSL's into Python, so the somewhat sketchy documentation shouldn't be too much of a problem. If the public key encryption algorithm you need to use is supported by M2Crypto, then you could very well use it to do your public key cryptography.
I found the M2Crypto test suite to be a useful example of using its API. In particular, the RSA (in test_rsa.py), PGP (in test_pgp.py), and EVP (in test_evp.py) tests will help you figure out how to set up and use the library. Do be aware that they are unit-tests, so it can be a little tricky to figure out exactly what code is necessary and what is an artefact of being a test.
PS: As I'm new, my posts can only contain one link so I had to delete most of them. Sorry.
Example
from M2Crypto import RSA
rsa = RSA.load_pub_key('rsa.pub.pem')
encrypted = rsa.public_encrypt('your message', RSA.pkcs1_oaep_padding)
print encrypted.encode('base64')
Output
X3iTasRwRdW0qPRQBXiKN5zvPa3LBiCDnA3HLH172wXTEr4LNq2Kl32PCcXpIMxh7j9CmysLyWu5
GLQ18rUNqi9ydG4ihwz3v3xeNMG9O3/Oc1XsHqqIRI8MrCWTTEbAWaXFX1YVulVLaVy0elODECKV
4e9gCN+5dx/aG9LtPOE=