How does machine A use the B.key.pub information in conjunction with the B.key information that is presumably presented when ssh'ing from B to A to authenticate that I'm a client allowed to connect?
SSH uses digital signatures. B uses the privatekey (for OpenSSH in B.key) to sign some data including the 'exchange hash' which covers all critical key-exchange parameters including nonces (which function as a challenge) and sends this signature along with the publickey in the AUTHREQ message (type 50). The privatekey is not 'presented' and indeed must never be sent or exposed to anyone else. A, the recipient, does two or three things depending how you count:
checks that the signature verifies for the 'exchange' data using the publickey; the details vary depending on the signature algorithm used, which OpenSSH calls the 'type' (i.e. type RSA uses the RSA algorithm or more exactly RSASSA-PKCS1v1_5; DSS uses the DSA algorithm; ECDSA uses the ECDSA algorithm; Ed25519 uses the Ed25519 algorithm which is an instantiation of the EdDSA algorithm). Since for a nonbroken signature scheme a valid signature can only be created using the privatekey, which should only be possessed by its owner, verifying the signature is considered proof the signature came from the key owner and noone else.
checks that the publickey is configured for the requested username (and the username itself is valid); for OpenSSH this is typically in the file ~/.ssh/authorized_keys but can be changed
OpenSSH, but not necessarily other implementations, also provides for some in-between cases. While a client publickey is not accepted at all if not present in authorized_keys or equivalent, and accepted if simply present, it can also be present in the file file with some option(s) specified for it and then it is accepted but only with conditions or limitations imposed by those option(s). See the man pages for details.
My gut feeling says that the A-host.key and A-host.key.pub come into it in reverse for mutual auth (i.e. client authenticating server as well as server authenticating client when the client initiates a connection, not just server authenticating client), but, where/when has machine B securely received any verifiable evidence to use as a basis for auth'ing A during this process?
Your first part is correct, except the 'mutual' usually focusses on the client side. For SSH, and also for SSL/TLS (which you didn't ask about), the server is essentially always authenticated using publickey cryptography. (Technically both protocols do have other options, but they are almost never used. SSL/TLS embeds the publickey in a certificate, while SSH normally does not, but that doesn't change the crypto significantly.) For both protocols it is technically optional whether and how to authenticate the client -- you can use publickey crypto, you can use something else, or you can not authenticate at all -- thus when we say 'mutual' auth it is usually to clarify or emphasize that the client is authenticated, since that's the only part that varies. In practice SSL/TLS is mostly used in situations, like the public web, where we do NO client auth at the communications level (many websites, e.g. Stack, allow anybody to at least connect but have logins at the application level for at least some content or functionality), while SSH is mostly used in situations where we do want client auth, and doing it at comms level is convenient, so we usually choose between SSH password and SSH publickey authentication of the client.
Yes, you (B) may not have known A's host key in advance. SSH was first developed as a replacement for the BSD 'r' programs (rsh, rcmd, rexec, etc) which were used mostly in what was then called a 'campus' environment and today we call an 'intranet' -- a portion of the network controlled by a single organization. In those environments you indeed could distribute the expected host key(s) out of band, especially for a fairly small and largely static set of servers. For example when you reported to work for a new job your supervisor or admin assistant might give you a PC, a bunch of CDs to install, and a pamphlet containing the names (or IP addresses) and host keys or fingerprints (see below) of the systems your job involved using. However, this often required some effort, so users who were busy, untrained/uncomfortable, or just lazy typically didn't use this check and just accepted any host key, which is (as you imply) insecure. This fairly soon evolved into a compromise called trust on first use where when you first connect you accept whatever key the host sends, but the client then remembers that key (for OpenSSH in ~/.ssh/known_hosts) and on subsequent connections accepts only that key. This helps some because an attacker can only succeed if they are present for, and identify, your first connection, though it is certainly not ideal.
If you want to do better, you might be able to, depending on details. See e.g. https://stackoverflow.com/questions/13791219/ssh-fingerprint-verification-for-amazon-aws-ec2-server-with-ecdsa and https://serverfault.com/questions/581367/amazon-ec2-instance-ssh-rsa-fingerprint -- but contrast (my) https://serverfault.com/questions/996828/how-can-i-confirm-ssh-fingerprint-when-connecting-to-a-new-amazon-ec2-instance-u . Note the fingerprint displayed to you by the ssh program -- and recorded in syslog etc -- is a hash of the actual publickey blob, which is sent in the protocol and stored in known_hosts; if you need to convert you can generally just use ssh-keygen -l but if necessary this can be done by hand and I've seen quite a few Qs or As on doing so, but I don't remember which Stacks; if you need that and can't find them I'll try to add.
