I installed a self-signed SSL in a Windows server. What should I do on the client so that they can establish a secure connection without any warning messages?
It depends on what client application is generating the warnings. Is it a web browser? If so, which browser?
For Internet Explorer, add the certificate (just the public key) to the user or computer's Trusted Root certificate store. The exact instructions for doing this vary somewhat depending on what Windows version the client is running.
Firefox doesn't use the Windows certificate store though, so you'd have to add it to Firefox's own store. In 3.6, that can be found in Tools - Options - Advanced - Encryption. Click the View Certificates button, and add it to the Authorities or Servers list.
I'm not sure about Chrome, Opera, or Safari.