The use of elevation changes in an undulating terrain surface can be an effective alternative for vehicle navigation in GPS-denied underwater environments, since subsea terrain elevation data can be obtained using sonar systems. The performance of terrain-referenced navigation varies significantly depending on how informative a given terrain is, however it is not straightforward to quantify the amount of information that can be provided by the terrain and predict the navigation performance. This study proposes a new terrain information measure by analyzing and quantifying the amount of information in terms of terrain roughness and uniqueness. The expected information is evaluated in the spatial frequency domain via Fourier transforms to maximize the computational efficiency of the quantification. To demonstrate the performance and utility of the proposed ideas, terrain-referenced navigation simulation results are shown and discussed.