Certificates – Implementation?

Since I’ve set up remote access at our company, users logging in are always presented with a warning that the certificate is invalid – which they can click through, of course.

I can’t seem to find a step-by-step solution to this problem, and I am trying very hard. Any suggestions?