The orthogonal time frequency space (OTFS) modulation has emerged as a promising modulation scheme for high mobility wireless communications. To enable efficient OTFS detection in the delay-Doppler (DD) domain, the DD domain channels need to be acquired accurately. To achieve the low latency requirement in future wireless communications, the time duration of the OTFS block should be small, therefore fractional Doppler shifts have to be considered to avoid significant modelling errors due to the assumption of integer Doppler shifts. However, there lack investigations on the estimation of OTFS channels with fractional Doppler shifts in the literature. In this work, we develop a high performing channel estimator for OTFS with the bi-orthogonal waveform or the rectangular waveform. Instead of estimating the DD domain channel directly, we estimate the channel gains and (fractional) Doppler shifts that parameterize the DD domain channel. The estimation is formulated as a structured signal recovery problem with a Bayesian treatment. Based on a factor graph representation of the problem, an efficient message passing algorithm is developed to recover the structured sparse signal (thereby the OTFS channel). The Cramer-Rao Lower Bound (CRLB) for the estimation is developed and the effectiveness of the algorithm is demonstrated through simulations.