Digital information and data are transmitted more often over the Internet now than ever. Free-access digital multimedia communication unfortunately provides virtually unprecedented opportunities to pirate copyrighted material. Therefore, the idea of using a digital watermark to detect and trace copyright violations has stimulated significant interests among engineers, scientists, lawyers, artists and publishers. In this chapter, we present robust high-capacity digital watermarking techniques based on genetic algorithm (GA) and chaotic map. A GA-based technique is presented to correct the rounding errors. The fundamental is to adopt a fitness function for choosing the best chromosome which determines the conversion rule of real numbers into integers during the cosine transformation. We develop a block-based chaotic map, which outperforms the traditional one by breaking local spatial similarity, to increase the amount of significant coefficients in the transformed image. We demonstrate the superiority of the proposed scheme in terms of better embedding capacity and lower message error rate. Furthermore, we show the proposed algorithm works well under some image-processing distortions, such as the JPEG compression, Gaussian noise, and low-pass filter.