how does the browser know this domain - CA mapping?
It doesn't. Or at least it doesn't know this from HSTS only. HSTS makes only sure that the target site is reached by HTTPS instead of HTTP. It does not care which CA has issued the certificate.
Public key pinning instead cares that a specific public key is used in the sites certificates or in the certificate of the issuer. There is predefined pinning for some sites like Facebook and there is pinning by using the HPKP header (not HSTS).
I have come across scenarios where we introduce a proxy which does ssl decryption fails on HSTS sites...eg. facebook gmail etc.
In case of properly setup MITM proxies as used inside companies or as installed by some AV products the proxy CA will be installed as trusted in the browsers/OS. This means certificates issued by the MITM proxy (using the proxy CA) will not cause an error/warning about an unknown certificate issuer. Additionally any certificates issued by this explicitly trusted non-standard CA will not be checked against public key pinning restrictions in current browsers. This means that a certificate for pinned site will be accepted without warnings even if it does not match the stored fingerprint, as long as it was issued by this non-standard but trusted CA.
If you still get a warning then the proxy is not properly setup. Any access to a new HTTPS site will then result in a certificate warning which the user explicitly has to ignore but hopefully does not. And the nice thing about public key pinning is that it does not allow users to ignore such warnings for sites protected with pinning but it will simply refuse to access such site then. This way it will also protect users against MITM attacks which are trained to click through any warnings.