Terrain-referenced navigation (TRN) is an effective strategy for vehicle navigation in GPS-denied environments or in situations where GPS signals are severely degraded. TRN uses topographic data to correct drift errors due to dead-reckoning or inertial navigation. While it has long been applied to aerial vehicle applications, TRN can be more useful for navigation in underwater environments where global positioning system signals are not available. TRN requires a geometric description of undulating terrain surface as a mathematical function or a look-up table, which leads to a nonlinear estimation problem. Due to the nature of this navigation strategy, the performance of TRN may vary significantly depending on how informative a given terrain is. However, it is not straightforward to quantify the amount of information that can be extracted from the given terrain and predict the expected navigation performance without extensive numerical simulations. This study presents a systematic procedure to evaluate the expected TRN performance by introducing a new terrain information measure that enables quantifying the amount of information for TRN in a computationally efficient manner. The proposed measure can be used in a path planning algorithm which maximizes the amount of terrain information to improve navigation performance. To demonstrate the performance and utility of the proposed ideas, an extensive set of TRN simulations and a field test using an unmanned surface vessel (USV) are performed, and the results are shown and discussed.