The problem of mean-square stabilization of a discrete-time linear dynamical system over a Markov time-varying digital feedback channel is studied. In the scalar case, it is shown that the system can be stabilized if and only if a Markov jump linear system describing the evolution of the estimation error at the decoder is stable -videlicet if and only if the product of the unstable mode of the system and the spectral radius of a second moment matrix that depends only on the Markov feedback rate is less than one. This result generalizes several previous data rate theorems that appeared in the literature, quantifying the amount of instability that can be tolerated when the estimated state is received by the controller over a noise-free digital channel. In the vector case, a necessary condition for stabilizability is derived and a corresponding control scheme is presented, which is tight in some special cases and which strictly improves on a previous result on stability over Markov erasure channels.