A watermarking method converts a watermark message into a Frequency Shift Keying (FSK) signal and embeds the FSK signal in a host signal. The spectral properties of the FSK watermark signal facilitate its detection, even in applications where the watermarked signal is corrupted. Because of these properties, the FSK watermark signal can perform the dual function of identifying the watermark's presence and orientation in potentially corrupted media, and also conveying a hidden message in the host signal. Such a watermark may be referred to as a self-orienting watermark.