The invention provides methods and apparatus for decoding multiple program information, e.g., audio, video or image information, in a communication system. In an illustrative embodiment, a multiple program decoder includes a deinterleaver for deinterleaving information corresponding to a set of frames, using a specified deinterleaving length. A given one of the frames includes information from each of at least a subset of the programs, and the frames are encoded using an outer code, e.g., a CRC code, RS code, BCH code or other type of linear block code, and an inner code, e.g., a convolutional code, turbo code or trellis coded modulation. The multiple program decoder includes an inner code decoder for decoding the inner code over one or more of the programs, and an outer code decoder for decoding the outer code for a selected one of the programs. The deinterleaving length of the deinterleaver and operating rate of the inner code decoder can be configured such that the multiple program decoder provides substantially instantaneous tuning within a given cluster of programs, or within a set of clusters each including multiple programs. The programs may, but need not, include jointly-coded audio programs. The invention may be implemented in numerous applications, such as simultaneous multiple program listening and/or recording, simultaneous delivery of audio and data, etc.