Given $\sigma$ a shift map, $m$ - a Markov measure, $C\_a$, $C\_b$ - cylinder sets.
Suppose $P \in C\_b$. The problem is to show the following
\begin{equation}
m(C\_a \cap \sigma^{-1}(P)) = \frac{m(C\_a \cap \sigma^{-1}(C\_b))}{m(C\_b)} m(P).
\end{equation}
This seems to be obvious, but I don't see how to prove this in a simple way for general $P$ (if $P$ is a cylinder set or an open set then the statement apparently holds).



The property of a Markov measure
There is a more conceptual explanation. This is a direct corollary of the Markov property formulated in "invariant form": **the past and and the future are conditionally independent with respect to the present.**


Your identity can be rewritten as 
$$
\frac{m(C\_a \cap \sigma^{-1}(P))}{m(P)} = \frac{m(C\_a \cap \sigma^{-1}(C\_b))}{m(C\_b)} \;,
$$
or
$$
m(C\_a|\sigma^{-1}(P)) \frac{m(\sigma^{-1}(P))}{m(P)} = m(C\_a|\sigma^{-1}(C\_b)) \frac{m(\sigma^{-1}(C\_b))}{m(C\_b)} \;.
$$


Now it is quite easy to see that the corresponding terms in the LHS and in the RHS are equal, which proves your identity. The formal justification is pretty straightforward if a bit tedious.


First, 
$$
m(C\_a|\sigma^{-1}(P)) = m(C\_a|\sigma^{-1}(C\_b))
$$
by the Markov property formulated above. In order to explain it on the formal level let me introduce some additional notation. By $\mathcal A\_n$ (resp., $\mathcal A\_m^n$) I denote the $\sigma$-algebra in the space $A^{\mathbb N}=\{a\_i\}\_{i=1}^\infty$ generated by the coordinate $a\_n$ (resp., the coordinates $a\_i$ with $m\le i\le n$), so that the cylinders $C\_a,C\_b$ belong to $\mathcal A\_1$, and the preimage $\sigma^{-1}(C\_b)$ belongs to $\mathcal A\_2$. Further, the set $P$ can be presented as 
$$
P=C\_b \cap Q \;,
$$
where $Q\in\mathcal A\_2^\infty$. Therefore,
$$
\sigma^{-1}(P)=\sigma^{-1}(C\_b) \cap \sigma^{-1}(Q) \;,
$$
where $\sigma^{-1}(Q)\in\mathcal A\_3^\infty$. Thus, the sets $A\_-=C\_a$ and $A\_+=\sigma^{-1}(Q)$ are conditionally independent with respect to $A\_0=\sigma^{-1}(C\_b)$. It means that
$$
\frac{m(A\_-\cap A\_0\cap A\_+)}{m(A\_0)} = \frac{m(A\_-\cap A\_0)}{m(A\_0)} \frac{m(A\_0\cap A\_+)}{m(A\_0)} \;,
$$
or 
$$
m(A\_-| A\_0\cap A\_+) = m(A\_-|A\_0) \;, 
$$
that is 
$$
m(C\_a|\sigma^{-1}(P)) = m(C\_a|\sigma^{-1}(C\_b)) \;.
$$
Note that this argument does not even require time homogeneity of the transition probabilities of the measure $m$. 


It remains to check that 
$$
\frac{m(\sigma^{-1}(P))}{m(P)} = \frac{m(\sigma^{-1}(C\_b))}{m(C\_b)} \;.
$$
This identity can be rewritten as 
$$
\frac{m(\sigma^{-1}(P))}{m(\sigma^{-1}(C\_b))} = \frac{m(P)}{m(C\_b)} \;,
$$
or, equivalently, as
$$
m(\sigma^{-1}(Q)|\sigma^{-1}(C\_b)) = m(Q|C\_b) \;,
$$
for which one has to require time homogeneity of the transition probabilities of the measure $m$ (its stationarity is still not necessary). 


