The present claims relate generally to steganographically encoding and decoding of audio signals. One claim recites a method of embedding auxiliary information in data representing audio. The method includes acts of: using at least a programmed electronic processor, altering data representing audio to include a sequence of bits of auxiliary information, said altering based on a carrier signal and corresponding to the sequence of bits, and said altering based on a local gain that varies within the data representing audio, the sequence of bits of auxiliary information including at least one fixed registration sequence for registration of the auxiliary information within the data representing audio and at least one message sequence, and in which the fixed registration sequence and the at least one message sequence are interleaved in at least some portions of the data, and in which the fixed registration sequence is provided in the data representing audio so as to allow determination of threshold levels associated with the auxiliary information; and repeating the altering of the data representing audio to include redundant instances of at least some of the auxiliary information including at least the fixed registration sequence. Of course, other combinations and claims are provided as well.