If you are in a windows domain you can distribute the public certificate of your "signing authority" using active directory. This will prevent IE from showing the untrusted warning. Otherwise you can install the public certificate into the users web browser and any certs you sign will show as trusted.
If you can give an idea of what platform/browser I can provide more specifics.
Brian,
Just my linux server and IE or firefox clients. I dont see many people connecting - just unknown of something poping up on a users screen that they dont know what to do about.
No active directory in use.
Jerry