Methods and apparatus for embedding a watermark are disclosed. An example method to embed media identification information in a compressed media data stream disclosed herein comprises reconstructing an uncompressed media data stream from the compressed media data stream, the uncompressed media data stream separate from the compressed media data stream, embedding the media identification information in the uncompressed media data stream to determine a watermarked uncompressed media data stream, and modifying a first mantissa value corresponding to a first transform coefficient associated with the compressed media stream to embed the media identification information in the compressed media data stream without uncompressing the compressed media data stream, the modification of the first mantissa value based on a difference between the first transform coefficient and a corresponding second transform coefficient generated from the watermarked uncompressed media data stream.