Maps and signs are embedded with plural-bit data in the form of digital watermarks. In one embodiment, the plural-bit data includes location information with respect to a map. A handheld reading device extracts the location information from the map. The reading device then compares the location information with a physical location of the device. Feedback is provided to help a device user to correlate the map location with the physical location. In another embodiment, signs are watermarked to provide navigational and informational aids. The watermarks may include unique identifiers, which allow database lookup of related information.