An information encoding apparatus and method, an information decoding apparatus and method, a recording medium, and a program make it possible to embed information without causing an increase in the amount of data of compressed audio signals. A spectrum measurer converts an audio signal from a time axis signal into a frequency axis signal. A compressor removes frequency spectra having levels below a minimum audible threshold value. An embedability determiner determines whether information can be embedded. A spectrum switcher embeds information in an audio signal by switching or by not switching predetermined first frequency spectrum and second frequency spectrum under the control of an information adder. The present invention is applicable to a disk recording apparatus.