Certificates are useful because even if you have a key pair, that doesn't mean you can just send someone your public key and the receiver will know that you control the corresponding private key. There must be some way for the receiver to associate that key with your identity (your "self"). Otherwise, an attacker could just send the server his public key, claiming that it's yours, and the message would be sent to him (or, conversely, you could receive a public key from a fake server, and receive a message that is properly encrypted, signed, but didn't come from who you think it came).
One way to exchange keys securely would be in-person, but that's cumbersome and not always feasible. Another option is to use a trusted third-party in the process - Person A signed the public keys of both Person B and Person C and associated each key with the holder's ID, so as long as B has a copy of A's public key he can verify that C's key matches C's ID (even if that key/certificate was sent through an insecure channel). Thus, B can send confidential messages to C (and, as pointed out in AJ Henderson's answer, the converse is also necessary if B wants to sign the message - C must have A's public key in order to verify B's identity).
So, answering your question, the certificates play a role in your process in the public key exchanging phase, everything else goes like you described. The contents of a certificate are one public key associated to one identifier (be it a domain name, or something else that uniquely identifies you, and that an honest third-party would not sign if they didn't know/trust you). And for who owns what, typically both own a list of trusted third-parties, used for verification, but nothing stops you from having also a list of known certificates from trusted individuals (in which case it doen't matter whether or not a third party signed them).
Update: a complete example, tailored to fit your scenario:
Alice (Server A) wants to send a message to Bob (Person B), with the help of their common acquaintance Charles Augustus. They have each a key pair, comprised of a private key (AA, BA and CA) and a public key (AB, BB and CB), and a certificate that associates their public key to their names (AC, BC and CC). Charlie signed his own certificate (CC$C) using his private key.
When Alice and Charlie met in-person, Charlie signed Alice's certificate using his private key (AC$C), after confirming that Alice controlled the corresponding private key (AA), that the certificate contained Alice's name (the server's domain name) plus public key (AB) and that she wasn't an impostor. Alice also got a copy of Charlie's certificate. Some time later, Bob did the same (getting BC$C, using his ID or some other proof-of-identity, since people don't have domain names).
When Alice wants to send a message to Bob, this is what happens:
- Bob sends his certificate (BC$C) to Alice;
- Alice confirms that the certificate has Bob's name, and that it was signed by Charlie;
- Since Alice has Charlie's certificate (CC$C), she uses the public key (CB) contained in it to verify the signature (made with the private key CA);
- now she trusts that Bob controls the private key (BA) that pairs the public key (BB) contained it Bob's certificate.
- "Now I sign the message with private key AA and encrypt it with public key BB on the server A. Person B verifies the signature with public key AB, and decrypts it with private key BA."
- Now Bob has the message, but he needs to be sure it really came from Alice. BTW Alice also sent her certificate (AC$C) together with the message (that's how Bob got the public key AB);
- Bob confirms that the certificate has Alice's name, and that it was signed by Charlie;
- Since Bob has Charlie's certificate (CC$C), he uses the public key (CB) contained in it to verify the signature (made with the private key CA);
- now he trusts that Alice controls the private key (AA) that pairs the public key (AB) contained it Alice's certificate.