This paper addresses the issue of estimating underwater vehicle trajectories using gyro-Doppler (body-fixed velocities) and acoustic positioning signals (earth-fixed positions). The approach consists of diffusion-based observers processing a whole trajectory segment at a time, allowing the consideration of important practical problems such as different information update rates, outages, and outliers in a very simple framework. Results of contraction theory are used to prove that the observers are convergent, i.e., stable in the incremental sense. Simulation and experimental results are presented to illustrate the potential of application of the method.