In a variety of emerging applications, there is a need to hide a sequence of bits in some host signal like a photograph or a radio transmission. Applications range from digital rights management and copyright notification and enforcement, to backwards-compatible upgrades to existing communication infrastructure, broadcasting, and covert communication. In such problems, there is an inherent tradeoff between the number of bits embedded, the robustness with which they are embedded, and the distortion the embedding incurs on the host signal. In this research, we show this problem is equivalent to an information theoretic problem of channel coding with side information at the encoder, and use the equivalence to characterize the tradeoff and develop the associated fundamental limits. We further introduce a practical and efficient encoding scheme we refer to as quantization index modulation (QIM), and a distortion-compensation techniques (DC-QIM), for achieving the fundamental limits. The key to the effectiveness of QIM is the way it ensures that the host signal is not a source of interference at the decoder. Indeed, data hiding systems based on DC-QIM are orders of magnitude more efficient than the more familiar data hiding systems based on spread-spectrum methods, in which there is host signal interference. This research underscores the importance of careful problem modeling to effective algorithm design.