The idea is that both sides prove that they know the same secret. The server sends the browser a challenge string called a nonce. The browser's reply contains both the nonce and an MD5 hash of various information including the nonce and its secret. The server satisfies itself that the nonce was valid, and tries to do the same hashing calculation. If the server and browser come up with the same answer, then they knew the same secret, and have managed to verify this without ever saying the secret.
The vulnerability to things like replay attacks is controllable on the server side in how it produces and verifies what the nonce was. Even if you can do a replay, you cannot use it against other pages because the complete requested URI is part of the hash. So a man in the middle can get the same page that they saw flying past a second ago.
Incidentally the shared secret is: Digest::MD5::md5_hex("$user:$realm:$password") So the server doesn't have to keep the actual password, but if you have used a one-way encryption mechanism which is incompatible with the above, then you will not be able to transparently move users to Digest authentication.
(Or at least this is how I read the documentation after scanning it quickly.)