Acquiring accurate channel state information and mitigating severe intersymbol interference are challenging for underwater acoustic communications with moving transceivers due to the rapid changes of the underwater acoustic channels. In this work, we address the issue using a superimposed training (ST) scheme with a powerful channel estimation method. Different from the conventional time-multiplexed training, training sequences with a small power are superimposed with symbol sequences. The training signals are transmitted over all time, leading to enhanced tracking capability to deal with time-varying channels at the cost of only a small power loss. To realize this, based on the belief propagation, we develop a message-passing-based bidirectional channel estimation (BCE) algorithm, where all messages are Gaussian, enabling efficient implementation. In particular, the channel correlations are fully exploited through a forward recursion and a backward recursion, thereby achieving accurat