How do Common Names (CN) and Subject Alternative Names (SAN) work together?

This depends on implementation, but the general rule is that the domain is checked against all SANs and the common name. If the domain is found there, then the certificate is OK for connection.

RFC 5280, section 4.1.2.6 says "The subject name MAY be carried in the subject field and/or the subjectAltName extension". This means that the domain name must be checked against both SubjectAltName extension and Subject property (namely its common name parameter) of the certificate. These two places complement each other, not duplicate each other. And SubjectAltName is a proper place to put additional names, such as www.domain.example or www2.domain.example

Update: as per RFC 6125, published in 2011, the validator must check SAN first, and if SAN exists, then CN should not be checked. Note that RFC 6125 is relatively recent and there still exist certificates and CAs that issue certificates, which include the "main" domain name in CN and alternative domain names in SAN. In other words, by excluding CN from validation if SAN is present, you can deny some otherwise valid certificate.

To be absolutely correct you should put all the names into the SAN field.

The CN field should contain a Subject Name not a domain name, but when the Netscape found out this SSL thing, they missed to define its greatest market. Simply there was not certificate field defined for the Server URL.

This was solved to put the domain into the CN field, and nowadays usage of the CN field is deprecated, but still widely used. The CN can hold only one domain name.

The general rules for this: CN - put here your main URL (for compatibility) SAN - put all your domain here, repeat the CN because its not in right place there, but its used for that...

If you found a correct implementation, the answers for your questions will be the followings:

Has this setup a special meaning, or any [dis]advantages over setting both CNs? You cant set both CNs, because CN can hold only one name. You can make with 2 simple CN certificate instead one CN+SAN certificate, but you need 2 IP addresses for this.

What happens on server-side if the other one, host.domain.tld, is being requested? It doesn't matter whats happen on server side.

In short: When a browser client connects to this server, then the browser sends encrypted packages, which are encrypted with the public key of the server. Server decrypts the package, and if server can decrypt, then it was encrypted for the server.

The server doesn't know anything from the client before decrypt, because only the IP address is not encrypted trough the connection. This is why you need 2 IPs for 2 certificates. (Forget SNI, there is too much XP out there still now.)

On client side the browser gets the CN, then the SAN until all of the are checked. If one of the names matches for the site, then the URL verification was done by the browser. (im not talking on the certificate verification, of course a lot of ocsp, crl, aia request and answers travels on the net every time.)

CABForum Baseline Requirements

I see no one has mentioned the section in the Baseline Requirements yet. I feel they are important.

Q: SSL - How do Common Names (CN) and Subject Alternative Names (SAN) work together? A: Not at all. If there are SANs, then CN can be ignored. -- At least if the software that does the checking adheres very strictly to the CABForum's Baseline Requirements.

(So this means I can't answer the "Edit" to your question. Only the original question.)

CABForum Baseline Requirements, v. 1.2.5 (as of 2 April 2015), page 9-10:

9.2.2 Subject Distinguished Name Fields a. Subject Common Name Field Certificate Field: subject:commonName (OID 2.5.4.3) Required/Optional: Deprecated (Discouraged, but not prohibited) Contents: If present, this field MUST contain a single IP address or Fully-Qualified Domain Name that is one of the values contained in the Certificate’s subjectAltName extension (see Section 9.2.1).

EDIT: Links from @Bruno's comment

RFC 2818: HTTP Over TLS, 2000, Section 3.1: Server Identity:

If a subjectAltName extension of type dNSName is present, that MUST be used as the identity. Otherwise, the (most specific) Common Name field in the Subject field of the certificate MUST be used. Although the use of the Common Name is existing practice, it is deprecated and Certification Authorities are encouraged to use the dNSName instead.

RFC 6125: Representation and Verification of Domain-Based Application Service Identity within Internet Public Key Infrastructure Using X.509 (PKIX) Certificates in the Context of Transport Layer Security (TLS), 2011, Section 6.4.4: Checking of Common Names:

[...] if and only if the presented identifiers do not include a DNS-ID, SRV-ID, URI-ID, or any application-specific identifier types supported by the client, then the client MAY as a last resort check for a string whose form matches that of a fully qualified DNS domain name in a Common Name field of the subject field (i.e., a CN-ID).