First - make sure you have the openssl package installed and have created a local Certification authority.
When talking about fqdn - the Full Qualified Domain Naeme is meant. This - to ensure you find your certificates after - and link them to the right service/site.
After that - create a private key with:

openssl genrsa -aes128 512/1024 > fqdn.key
Generating RSA private key, 512 bit long modulus
......................++++++++++++
....++++++++++++
e is 65537 (0x10001)

This will ask you for a password. If for any reason you don't want a password to be entered every time you want to use the certificate - skip the -aes128 part.
Once the Key created - you need to create a certification request

openssl req -new -key fqdn.key > fqdn.csr
You are about to be asked to enter information that will be incorporated
into your certificate request.
What you are about to enter is what is called a Distinguished Name or a DN.
There are quite a few fields but you can leave some blank
For some fields there will be a default value,
If you enter '.', the field will be left blank.
-----
Country Name (2 letter code) [AU]:US
State or Province Name (full name) [Some-State]:New York
Locality Name (eg, city) []:New York
Organization Name (eg, company) [Internet Widgits Pty Ltd]:Internet Widgits Pty Ltd
Organizational Unit Name (eg, section) []:Demo Certificate Creation
Common Name (eg, YOUR name) []:www.newyork.com
Email Address []:postmaster@newyork.com

Please enter the following 'extra' attributes
to be sent with your certificate request
A challenge password []:
An optional company name []:

Make sure the Common Name matches the Full Qualified Domain name of the Service you want to use the certificate for.
Once the request created - you need to let your local CA sign the certificate using:

openssl ca -policy policy_anything -out fqdn.crt -infiles fqdn.csr
[... Loads of stuff removed ...]
Certificate is to be certified until Dec 29 09:29:23 2006 GMT (365 days)
Sign the certificate? [y/n]:y
1 out of 1 certificate requests certified, commit? [y/n]y

Now you're done.
If you're looking to create a pem-file - here is a little help for it - used b.e. to create a Key for Cyrus-Imap.

dd if=/dev/urandom of=random.rnd count=1
openssl req -new -x509 -days 365 -nodes -out fqdn.pem -keyout fqdn.pem
openssl gendh -rand random.rnd 512 >> fqdn.pem
openssl x509 -subject -dates -fingerprint -noout -in fqdn.pem

This will generate you a fine certificate for use with cyrus.