The authentication uses public key authentication, which means that instead of providing a password, you provide a private key matched to a public key that your server has stored and associated with you. You don't actually send the private key (it is private, after all), but you prove that you are in possession of it by performing encryption/decryption/signing with it that is complementary to the operations performed with the public key. For example, a payload encrypted with your private key may be decrypted with your public key, and by virtue of the fact that your public key was used to decrypt the data, the host knows that it was encrypted with your private key.
You may know that the server is who they say (and not man-in-the-middle - MITM) in the same way that they know who you are - by storing their public key. You can either turn off StrictHostKeyChecking upon first connect, which will store the public key (or at least its fingerprint) in your trusted cache. If you're worried about a MITM attack upon the initial connect, you can get the fingerprint through a separate channel, then manually validate it upon first connect (your ssh client will show you the fingerprint and ask you to accept or reject). Similarly, you would need to get your public key to the server via another channel so they can ensure it wasn't generated on the fly by a MITM.
In the SSL world, this storing of the server key isn't necessary, as they make use of certificates to validate, but that's not the case with SSH.
DragonsOfWine's statement that "there is no way for you to guarantee you are talking to the right machine until you get onto it and do some digging" is a bit misleading. A MITM may simply forward all traffic both directions without modifying it, or modifying it only in a limited set of circumstances. So when you list your documents and see the 5 files you expected, that is no indication that a MITM attack didn't take place. On the other hand, if you go to the ssh public key directory and print (cat) it out, that would most likely give you your validation. But there would still be a small risk that the MITM software modified that data as it came.