Just follow one of the many step by step instructions for creating your own certificate with OpenSSL but replace the “Common Name” www.example.com with *.example.com.
Usually you have to keep a bit more money ready to get a certificate for this.
> openssl req -new -x509 -keyout cert.pem -out cert.pem -days 365 -nodes
Country Name (2 letter code) [AU]:DE
State or Province Name (full name) [Some-State]:Germany
Locality Name (eg, city) []:nameOfYourCity
Organization Name (eg, company) [Internet Widgits Pty Ltd]:nameOfYourCompany
Organizational Unit Name (eg, section) []:nameOfYourDivision
Common Name (eg, YOUR name) []:*.example.com
Email Address []:webmaster@example.com
(Sorry, my favorite howto is a german text that I don’t have readily available and can’t find currently, thus the ‘many’ links)
Edit in 2017: The original answer to this question is from 2009, when the choice for certificates did not include fully automated and free options like Let’s Encrypt. Nowadays (if the “domain-validated” certification level of Let’s Encrypt is enough for your purpose) it’s trivial to obtain individual certificates for each and every subdomain. In case you need a higher trust level than domain-validated, wildcard certificates are still an option.
Also from 2017, note the comment below, by @ha9u63ar:
According RFC 2818 sec. 3 using CN for host name identification is not recommended anymore (deprecated) Subject Alternative Name (SAN) seems to be the way to go.
My answer to this comment: I trust that nowadays any CAs that issue Wildcard certs will have a proper set of instructions. For a self-signed quick fix, I’d not worry. On the other hand, with LetsEncrypt being around these days, it’s been a long time since I’ve created a self-signed certificate. Gee, this answer really shows its age.