This paper considers stochastic consensus problems over lossy wireless networks. We first propose a measurement model with a random link gain, additive noise, and Markovian lossy signal reception, which captures uncertain operational conditions of practical networks. For consensus seeking, we apply stochastic approximation and derive a Markovian mode dependent recursive algorithm. Mean square and almost sure (i.e., probability one) convergence analysis is developed via a state space decomposition approach when the coefficient matrix in the algorithm satisfies a zero row and column sum condition.Subsequently,we consider a model with arbitrary random switching and a common stochastic Lyapunov function technique is used to prove convergence. Finally,our method is applied to models with heterogeneous quantizers and packet losses, and convergence results are proved.