I didn't find a lot of info on this, so I thought I would post here to clarify things for some people based on our experience. In our case we have custom Apex code calling out to server on our local domain xxxxx.net. We had to renew a cert that was expiring. This cert was incorrectly put on both ends, the xxxxx.net end, and on the salesforce end. An admin removed the cert from the salesforce end, and everything still worked (because this was not needed--I'll explain in a minute). Then another admin removed the cert on the server end, and replaced it with one that is not expired, and we got errors. These changes happened around the same time, so it was difficult to tell what caused the error. The error we got in the Developer Console was this:

EXCEPTION_THROWN [123]|System.CalloutException: PKIX path building failed: sun.security.provider.certpath.SunCertPathBuilderException: unable to find valid certification path to requested target

When we checked the cert using DigiCert's free cert checking tool, it returned that the cert was "Ok", because technically it was, but the interesting thing was that Salesforce did not like the new cert because it did not have the intermediate certificate chain. In the process of trying different ways to connect, we noticed that CURL said:

SSL certificate problem: unable to get local issuer certificate

but it did not have this error for other places where we had this cert installed. A quick google search indicated the intermediate certificate chain as the issue: namely that it was missing.

So, Salesforce has an article that states that it will not trust any server it is connecting to without the server having a CA-signed cert installed. This is correct. This must be installed on the server that Salesforce is connecting to. Jia Hu is correct: a certificate does not need to be on the Salesforce end (if your server does not require one to be presented to it). Only if you choose to require Salesforce to present a certificate (in this case it would be a CLIENT certificate) then this is when you would use the buttons "Create Self-signed Certificate" or "Create CA-signed Certificate".
My understanding is that from Salesforce, you can present it in one of 2 ways:
1. Directly using the "Unique Name" or "Alias" which is specified at the creation of the cert:

// API Callout   
        HTTP h = new HTTP();
        HTTPRequest r = new HTTPRequest();
        r.setClientCertificateName('unique_name');

2. Using a "Named Credential":

There may be other ways, but these are what I am aware of.
When making a "New Named Credential" you have some options. You can use OAuth, or just basic username and password auth, or you can use a certificate...I think you can use both a cert and username/password but don't quote me on that.

In our case, our code was written to use a named credential. All that was required by our server was a username and password (don't worry--we have other security measures in place), so we only needed to choose basic authentication in the Named Credential and enter the username and password it would use to connect to our server.

So the moral of the story is that you can get this working with this minimal configuration:

1. External Web Server side:
   1. A user account (use a long randomly generated password)
   2. A CA-signed (REQUIRED!) certificate installed (to prove to Salesforce you are legit): either wildcard (xxxxx.net) or server (server.xxxxx.net) --- include intermediate cert chain (REQUIRED!)
2. Client (Salesforce) side:
   1. A Named Credential - Basic Authentication (enter username and password of the user account you created on the server)