If $P$ is a regular transition probability matrix then $P^{n^2}$ has no zero element
[Edited out a typo --- thanks, Ilya]
EDIT: Theorem. If $A$ is an $n\times n$ matrix with nonnegative entries, and some power of $A$ has only positive entries, then $A^q$ has only positive entries, where $q=n^2-2n+2$. This is sharp; there is a matrix for which $A^{q-1}$ does not have only positive entries.
The Theorem is due to Wielandt. A nice discussion appears in Hans Schneider, Wielandt's proof of the exponent inequality for primitive nonnegative matrices, Linear Algebra and its Applications 353 (2002) 5-10. Schneider also refers to Section 3.5 of Brualdi and Ryser, Combinatorial Matrix Theory.
See also page 11 of this webpage. Also Holladay and Varga, On powers of non-negative matrices, Proc AMS (1958) 631-634.
MORE EDIT. The smallest exponent $r$ such that $A^r$ has only positive entries has been denoted $\gamma(A)$ in the literature; it is sometimes called the exponent of $A$, sometimes, the index of primitivity. By Wielandt, $$\gamma(A)\le n^2-2n+2$$ So the question arises, given $n$, for which $m$ with $1\le m\le n^2-2n+2$ is there an $n\times n$ matrix $A$ with $\gamma(A)=m$?
The question is answered in
Lewin and Vitek, A system of gaps in the exponent set of primitive matrices, Illinois J Math 25 (1981) 87-98, MR 82h:15026
Jia Yu Shao, On a conjecture about the exponent set of primitive matrices, Lin Alg Appl 65 (1985) 91-123, MR 86k:15013
Ke Min Zhang, On Lewin and Vitek's conjecture about the exponent set of primitive matrices, Lin Alg Appl 96 (1987) 101-108, MR 88j:15019.
Lewin and Vitek showed that given arbitrary integers $n$ and $t$ there is no $n\times n$ matrix $A$ with $$n^2-tn+(t+1)^2/4\lt\gamma(A)\lt n^2-(t-1)n+t-2$$ (the cases $t=3$ and $t=4$ go back to a 1964 paper of Dulmage and Mendelsohn). They further conjectured that there are no gaps in the exponent set below $1+(n^2-2n+2)/2$.
Shao went some way toward establishing the Lewin-Vitek conjecture but also showed it was false for $n=11$.
Zhang then proved that $n=11$ is the only exception to the Lewin-Vitek conjecture.
[What follows is wrong stuff from an earlier edit, retained here for historical reasons. Please ignore.
[If $P^k$ has the same number of zeros as $P^{k+1}$, then $P^r$ has that many zeros for all $r\ge k$. So in order for $P$ to be regular, each power of $P$ must have at least one zero fewer than the previous power. Since $P$ can't have more than $n^2$ zeros....
[I think $n^2$ can be sharpened to $n(n-1)/2$, though I'm not prepared to give a proof or a reference. I don't know whether one can achieve every value between $1$ and $n(n-1)/2$.]