The short answer is, you don't. To get a fully-trusted certificate, you must pay a trusted CA a pretty good sum of money (per year). A self-signed certificate will never be trusted by browsers for the simple reason that anyone can create them.
However, the connection IS still fully encrypted, despite the lack of trust. We run an Exchange server with a self-signed certificate. All our users have to allow access into the site, and it's a bit of a pain, but the connection is still encrypted and secure.
But if you want to have a fully-trusted site, then you must get a certificate from a company such as Comodo, Thawt, Verisign, GoDaddy, or another similar company.
P.S. If the error you are referring to is coming from FF, this appears to be a bug in FF itself where it (sometimes) won't allow a connection to the server if the cert is untrusted. A quick google
search reveals some more details on this.