A method and apparatus for brokering data embedding services. The method comprises the steps of receiving a request in an embedded data brokering system to embed the auxiliary data in the media program, determining if the auxiliary data may be embedded into the media program, negotiating a schedule for broadcasting the media program with embedded auxiliary data with the media program provider, transmitting the negotiated schedule for broadcasting the media program with the embedded auxiliary data to the media program provider, steganographically embedding the auxiliary data in the media program while collecting billing information regarding the embedded data, and providing the media program and the embedded auxiliary data to the media program services subscriber for broadcast according to the broadcast schedule.