For traditional watermarking techniques based on fractal coding, watermarking format is limited to binary sequence 0,1, thus incapable of gray-scale image embedding. In this paper, a novel algorithm feasible for gray-scale watermarking embedding is proposed. To embed watermarking directly into decoding parameters, the host image is encoded with orthogonal fractal coding techniques. Because of the mean-invariant characteristics of fractal encoding parameters during iterations, the watermarking can be embedded into them. On the other hand, fractional calculus pseudo-random sequence has solved the problem that how to enhance the security of embedded watermarking and makes it possible for gray-scale watermark to be embedded during fractal encoding process. Experimental results indicate that proposed algorithm brings little contamination upon the original image，and the extracted watermarking is of good quality. The encryption for gray-scale watermark with fractional differential sequence shows good performance.