A private-public key-pair is easy to generate. Likewise, an "uncertified" certificate may be generated with little effort, but obtaining a trustworthy certificate from a CA necessarily requires some work, time, and (usually) cost. It involves interacting with the CA to prove identity, and waiting for the CA to digitally sign the certificate.
Alternatively OpenSSL may be used. The reader is referred to the OpenSSL Key HOWTO for instructions on generating key-pairs and to the OpenSSL Certificate HOWTO for generating certificates. It is recommended that keys with a length of at least 768 bits are used. OpenSSL may be obtained from http://www.openssl.org/source/ or http://www.openssl.org/related/binaries.html.
Next: Server and Client Validation