In this work a new location fingerprinting-based localization algorithm is proposed for an underwater medium by utilizing ultra-wideband (UWB) signals. In many conventional underwater systems, localization is accomplished by utilizing acoustic waves. On the other hand, electromagnetic waves haven't been employed for underwater localization due to the high attenuation of the signal in water. However, it is possible to use UWB signals for short-range underwater localization. In this work, the feasibility of performing localization for an underwater medium is illustrated by utilizing a location-based fingerprinting approach. Existing algorithms for an indoor environment are evaluated in this project for an underwater medium. These algorithms are based on a neural networks or maximum likelihood estimator. Further, we also consider a classical k-nearest neighbors (KNN) approach. In addition, by employing the concept of compressive sampling, we propose a sparsity-based localization approach for which we define a system model exploiting the spatial sparsity. Moreover, a recently proposed grid mismatching algorithm is also adapted to the current localization framework and its performance is evaluated. Finally, the performance of the proposed methods is compared with the existing fingerprinting-based localization approaches.