Audio steganography methods and apparatus using cepstral domain techniques to make embedded data in audio signals less perceivable. One approach defines a set of frames for a host audio signal, and, for each frame, determines a plurality of masked frequencies as spectral points with power level below a masking threshold for the frame. The two most commonly occurring masked frequencies f1 and f2 in the set of frames are selected, and a cepstrum of each frame is modified to produce complementary changes of the spectrum at f1 and f2 to correspond to a desired bit value. Another aspect of the invention involves determining a masking threshold for a frame, determining masked frequencies within the frame having a power level below threshold, obtaining a cepstrum of a sinusoid at a selected masked frequency, and modifying the frame by an offset to correspond to an embedded data value, the offset derived from the cepstrum.