In that document, he proposed two different systems.

The first transmits two tuples for every bit of the message. In pseudo-ish code:

    for(i = 0; i < message_bits.length; ++i){
        send( (sequence_number, 0, (message_bits[i] == 0? HMAC(shared_key, sequence_number . '0') : rand())) );
        send( (sequence_number, 1, (message_bits[i] == 1? HMAC(shared_key, sequence_number . '1') : rand())) );
    }

Without knowing the HMAC key, the only information exposed is the length of the message. Without the HMAC key, you can't tell whether '0' or '1' (both of which are sent, for every bit in the message) is the correct bit.

The second works in a slightly different way. You take a message, and transform it into a package in such a way that one must determine the entire package contents before being able to decode any part of the package. (Rivest's proposal for such an 'All-or-Nothing Transform' can be found in [1]).

Next, you packetize that transformed package. Rivest proposes blocks of 1024 bits, but it could be anything. The point is you can't send (2^1024 - 1) 'chaff' blocks, which would be required to not leak any information about a 1024-bit message block.

But, crucially, you must determine which is the correct block for every sequence number sent. So, if one includes just one 'chaff' block for each 'wheat' block (so there is one wheat and one chaff block for each sequence number), and sends n blocks, then an attacker who doesn't know the HMAC key would need to choose the right combination of blocks of all sequence numbers--a 1 in 2^n chance--before being able to decode your message.

If one splits an all-or-nothing transformed message into at least 256 blocks and sends one 'chaff' block with each 'wheat' block, you could be pretty sure the message remains confidential. Of course, this assumes all those pesky security assumptions about the random number generator, transform, and HMAC function hold up.

[1]: http://theory.lcs.mit.edu/~cis/pubs/rivest/fusion.ps

Keep reading: the first example is a bit misleading (for the reason you state) and the article gets more interesting.

They deal with this problem by coding the message with single-bit packets, always contrasting 0s with 1s.

Yup, that was the critical piece I was missing. Thanks!