On my host, which is Debian:
cd /etc/ssl/certs
openssl req -new -x509 -nodes -out imapd.pem -keyout imapd.pem -days 365
It will ask a few questions, give a few answers...Done!
I had forgotten how since I did it last almost 2 years ago. I have just been putting up with the annoying warning when I connect to my server. Link here: http://www.knowplace.org/pages/howtos/linux_imapd_with_ssl_howto.php