The EthHash algorithm works by defining two critical structures:
A 16 MB cache, which is generated from a seed, which is changed every epoch. Every node (including light clients) generates this cache and stores it.
A 1 GB DAG, which is generated from the cache in such a way that each part of the DAG depends on a small number of pseudo-randomly chosen elements from the cache.
You are correct in that the mix hash is essentially generated from a collection of pseudo-random pieces of the DAG, but it is important to note that these pieces are chosen in a deterministic way that depends only on the block header (not including the mixhash) and the nonce.
In order to be able to mine quickly, miners pregenerate the full DAG and store it in memory, so that lookups are fast, because the miner needs to try millions of nonces in order to find a successful one.
Each round of the algorithm only requires 64 lookups to the DAG, however. This means that given a nonce, a non-mining client can use the cache to generate only the small portion of the DAG that is actually used.
You can see the line of code in Geth which performs the difficulty check during block verification here, which calls this code, which then computes the actual mixhash using this function.
As for the second (and IMO more interesting) part of your question, I can't seem to find where Geth checks the mixhash generated from the nonce against the one in the block header. I may be missing something, and I'll get edit this answer later