A digital watermarking method performs tonal detection on a signal (e.g., audio) to identify tonal and non-tonal components. These components are analyzed to compute appropriate weighting of a digital watermark for the tonal and non-tonal components. This tonal detection method is also used in recovering the watermark. A decoding method performs tonal detection on a watermarked signal, computes weights for tonal and non-tonal components, and recovers the embedded watermark using the weights. The same or different watermark embedding schemes may be used to embed digital watermarks in the tonal and non-tonal components. Tonal analysis is used in conjunction with frequency and temporal shaping to adapt the digital watermark to the signal in which it is embedded.