If you review the cryptography (keys and signing) section of the RFC
https://tools.ietf.org/html/rfc6376#section-3.3
The cryptography aspects that are in play are RSA 1024+bit Keys and SHA-1 and SHA-256 hashing.
You do not need a public CA to perform any of these functions. In fact a public CA will never generate private keys for you (as it means they will be able to intercept or decrypt all your traffic). You can generate your own RSA key and most crypto libraries like OpenSSL will do the signing for you.
Depending on your mail server it may generate keys for you automatically.
There is also a great list of the functionality provided by various servers and clients:
http://www.dkim.org/deploy/index.html
So you may just need to configure the right bit of the mail server. Mdaemon for example does most of the heavy lifting for you.
Review the wikipedia page as it’s quite good: http://en.wikipedia.org/wiki/DomainKeys_Identified_Mail
Andrei