Hey Adam,
You’ll need to buy a certificate from one of the certificate authorities supported by IE (e.g. from one that pays Microsoft for the privilege of not generating a warning). Installing such a certificate is covered in the FAQ.
You can, within your own organization, create your own certificate server and avoid this message on systems setup to accept those certificates…but you can’t expect your customers to configure their browsers to know about your certificate server.
There’s no workaround, I’m afraid, and even if you buy a certificate, it only applies to one domain (and possibly subdomains, if you get a wildcard certificate).
The reason this warning occurs is because certificates perform two functions:
-
The obvious encryption of data. This function protects passwords and such from prying eyes out on the big bad internets. An unequivically good thing.
-
Provide a guarantee that you are connecting to the site you think you are. This one is more subtle (and most folks don’t even realize this is one of the functions of an SSL protected website), and less important to most folks. This function protects against man-in-the-middle attacks. In other words, if you pay attention to the warnings, it can protect against someone poisoning DNS and pointing your domain name to some other server somewhere that looks like yours but is really just there to collect login details. This one requires more work than just sniffing traffic on the part of attackers, but is also a real security threat.
In short, getting a real certificate is recommended, but not economically feasible for the majority of non-commercial (those that don’t store sensitive data) websites.
You have options, of course…you can generate a custom certificate that does provide all of the information specific to your server (company name, etc.) and then train your customers in how to accept that certificate on first visit–this still doesn’t really provide the end-to-end guarantee that a certificate from someone like GeoTrust or GoDaddy does on the first visit, but it does insure that if they hit your site correctly the first time (and tell their browser to learn the certificate) any future visits will be protected the same as if the certificate were a “real” certificate.
Clear as mud?
In short, you’re making decisions about tradeoffs. The ideal situation is for all of us to have unlimited budgets, and we buy certificates for every domain every year, but I don’t live there, and I’m guessing neither do you. 
So, we’re walking the security line as best we can. With a little extra effort on your part, you can go a couple of steps farther toward protecting your users and your server. With a little extra effort and a little extra cash, you can provide reasonable expectations of both good security and a guarantee of end-to-end communication free from tampering.
I’ll point out that these problems apply to any secured communication. Mail servers, POP/IMAP servers, web servers like Apache, SSH, all have the problem of securing data and insuring an end-to-end connection. Most of them handle it with the same certificate mechanisms, and you can often use the same certificate (or a different format of the same certificate) for all of those purposes (except SSH). In other words, you can secure Webmin, Apache, Postfix, and Dovecot with the same certificate, assuming they all work on the same domain name.
Another option is to skip encryption altogether. I don’t recommend this, but it won’t generate any warnings.
Anyway, I hope this helps.