In this article, we propose a joint halftoning and data hiding technique for color images. To ensure high quality of the printed image, the color direct binary search (CDBS) iterative halftoning algorithm is used. The proposed approach uses the commonly available cyan, magenta and yellow colorants to hide data in the chrominance channels. Orientation modulation is used for data embedding during the iterative CDBS halftoning stage. The detector is using PCA-learned components to extract the embedded data from the scanned image. Experimental results show that this proposed CDBS-based data hiding method offers both higher data hiding capacity and higher robustness to the print-and-scan channel when compared to the state-of-the-art grayscale counterpart method. The relatively high correct detection rate make this approach suitable for applications which require exact extraction of embedded data in prints.