The rapid growth in the demand and consumption of the digital multimedia content in the past decade has led to some valid concerns over issues such as content security, authenticity, and digital rights management. Multimedia data hiding, defined as imperceptible embedding of information into a multimedia host, provides potential solutions, but with many technological challenges. In this thesis, we address several fundamental issues in this field, which provide the framework for the design of practical techniques that can seamlessly be deployed in real-world applications. The first problem we address is that of embedding high volume of information in an image without incurring any perceptual distortion, and achieve robustness against compression, additive noise, and image tampering attacks. Key to this is the use of image-adaptive perceptual criteria, and a coding framework that em- ploys turbo-like codes, leveraging the huge advances in coding theory made over the last decade. Next, a hybrid digital-analog scheme is proposed for hiding an image into another image in such a way that the quality of the recovered image improves as the attack gets milder. This graceful improvement is permitted by a novel joint source-channel coding scheme. We then present techniques that allow robust embedding of hundreds of bits into images, in a manner that survives printing followed by scanning. Autocalibration methods, such as automatic algorithm for undoing rotation induced by the scanning process, play a key role. Finally, we present a framework for the design of perfectly secure covert communication (steganographic) techniques that can potentially evade any statistical steganalysis of the stego signal.