Image steganography is a smart technique of embedding the secret information into the cover image without any visual loss. As fractal image represents self-similar patterns, more number of bits can be embedded. A color palette based image steganography algorithm for the iterated Julia-set fractal image is proposed. The color palette is created and sorted based on the illumination values of the pixels. The palette is being scanned for embedding the secret bit, and the palette index is modified based on the secret bit's value. For improving the robustness of the algorithm, a random pixel selection technique is suggested and implemented effectively. The proposed algorithm gives maximum peak signal to noise ratio (PSNR), up to the number 61, and Normalized Correlation (NC) of 0.999 for approximately 50 images.