Introduction
AsicBoost speeds up Bitcoin mining in general (for ASICs and CPUs alike) by reducing the frequency of computing one part of the SHA-256 calculation.

A Bitcoin block header is 80 bytes long. It fits in 2 blocks for SHA-256 hashing. It gets hashed into a 32-byte value, then hashed again (1 block) to get the final value that is compared to the threshold.

Pseudocode
The conventional way to do Bitcoin mining looks like this:

while True:
    blockHeader = ...  # based on Merkle root and other fields
    sha256Block0 = sha256Expand(blockHeader[0 : 64])
    midState = sh256Compress(sha256InitVector, sha256Block0)

    for i in range(2**32):  # Try nonces
        blockHeader.nonce = i
        sha256Block1 = padAndExpand(blockHeader[64 : 80])
        singleSha = sh256Compress(midState, sha256Block1)

        sha256Block2 = padAndExpand(singleSha)
        doubleSha = sh256Compress(sha256InitVector, sha256Block2)
        if doubleSha < target:
            miningSuccessful(blockHeader)  # Jackpot!

Notice above that the inner loop has 2 calculations of block expansion and 2 calculations of block compression.

Now what AsicBoost proposes is that we somehow find a bunch of blockHeader values where sha256Block0 is different but sha256Block1 is the same. Because the Merkle root field straddles both hashing blocks, it means we need to group candidates by the last 4 bytes of the Merkle hash. Now the mining algorithm looks like this:

while True:
    blockHeader = ...  # based on various fields
    candidates = dict()  # 4 bytes -> sets of blocks
    for i in range(...):  # Generate the more the merrier
        tempBh = blockHeader.randomizeMerkle()
        sha256Block0 = sha256Expand(tempBh[0 : 64])
        tempBh.midState = sh256Compress(sha256InitVector, sha256Block0)
        candidates[tempBh.merkleRoot[28 : 32]].add(tempBh)

    for i in range(2**32):  # Try nonces
        for key in candidates:
            tempBh = candidates[key][0]
            tempBh.nonce = i
            sha256Block1 = padAndExpand(tempBh[64 : 80])

            for tempBh in candidates[key]:
                singleSha = sh256Compress(tempBh.midState, sha256Block1)
                sha256Block2 = padAndExpand(singleSha)
                doubleSha = sh256Compress(sha256InitVector, sha256Block2)
                if doubleSha < target:
                    miningSuccessful(blockHeader)  # Jackpot!

Now notice that the inner loop performs 1 calculation of block expansion per candidate group, and then 1 calculation of block expansion plus 2 calculations of block compression per candidate block header.

Thus the technique wins over conventional mining when most candidate groups have more than one candidate, and that the overhead of generating and sorting candidates exceeds the gains from saving at most one calculation of block expansion per candidate.