A multi-channel embedded data technique allows for embedding data, such as watermarks into multiple channels of audio, video, multi-media, and other digitized content streams. Two or more of the channels may be utilized. The embedded data may be segmented within each channel, and these segments may start and stop at identical times, or may be staggered or offset from one another. The available payload may be used for different data, or redundant data, providing enhanced reliability. Staggering allows for more rapid availability of at least some of the embedded data segments. References may be used between channels and between data streams to provide for highly complex configurations of encoding and decoding of the embedded data.