A lot of people seem confused about how merged mining of cryptocurrencies sharing a hashing algorithm works, so I thought I'd write this up. This is more of a brief process overview than FAQ as there's been several of those, but feel free to ask any questions here or in the /r/dogecoin thread.
To mine any block, you construct a block header and include the previous block's header hash and a Merkle root hash. The Merkle root is the parent hash from a tree of hashes constructed from the potential transactions that will be included in the block. Each leaf of the tree (a transaction) is hashed, then each parent node is built by hashing two child hashes. This continues up the tree until the root hash is calculated that includes all of the child hashes, meaning that if the Merkle root is valid, the entire block's worth of transactions must also be.
The block header includes a few other important values. The difficulty target (which decreases as the difficulty rises), nonce, and timestamp. With rising difficulty, finding a valid hash becomes more time consuming because a miner's valid hash must be lower than the difficulty target to be accepted by the network. This restricts the space of accepted hashes. Each time an invalid block hash is calculated, the nonce is incremented and the header is hashed again until a match is found.
When the header nonce overflows (it's a 32-bit number), the Merkle root is recalculated with its own nonce. The timestamp or transaction contents may also be adjusted when generating this new header and the search process resumes on the new block header. This is how the search space is large enough to support finding a small enough block hash.
Merged Mining Changes
If two coins share a hashing algorithm, you can adopt a system that allows you to construct a block header that will be valid for both. The first step is selecting a parent and a child blockchain, as the child will need to be forked (why in a bit). In this example, consider Litecoin as the parent and Doge as the child.
To mine a merged hash, you select a difficulty equal to the higher difficulty of either blockchain for the header. Then you construct block headers for both. In the Litecoin Merkle tree, you include the Dogecoin block header hash as a transaction. In this way, solving the Litecoin block will also be verifying the Dogecoin transactions with the same proof of work.
Miners work units are generated from the Litecoin block header and mining continues as usual, looking for a hash that matches that block. If we solve at Litecoin's difficulty, the block is submitted to the Litecoin network with the Litecoin header, the Litecoin transaction set, and has one extra transaction that the Litecoin network ignores (containing the Dogecoin block header hash). Assuming Litecoin has the higher difficulty, this will also result in a Dogecoin block being discovered.
If we solve at or above Dogecoin's difficulty, both block headers are submitted to the Dogecoin network, with Dogecoin's transaction set. This is why we would need to fork, Dogecoin client would need to be able to accept blocks containing both and accept the hash included in the Litecoin header as proof of work (since it verifies the Dogecoin block header).
The result is slightly more data in Dogecoin's blockchain and one extra transaction per solved block in the Litecoin chain. A relatively small amount of overhead for the potential benefits of pooling the hash rate.