Some necessary conditions for $Z$ to be Markov are easy to understand and to write down. 

For every $y$, $y'$ and $y''$ in the state space $S$ of $Y$, write $p_3(yy'y'')$ for the probability that $[Y_t=y,Y_{t+1}=y',Y_{t+2}=y'']$, which is independent of time $t$. Assume that $Z=\phi(Y)$. For every $z$, $z'$ and $z''$ in $\phi(S)$, write $q_3(zz'z'')$ for the sum of $p_3(yy'y'')$ over every $y$, $y'$ and $y''$ such that $z=\phi(y)$, $z'=\phi(y')$ and $z''=\phi(y'')$. Then a necessary condition is that $q_3$ can be factorized, in the sense that there exist functions $r$ and $s$ such that $q_3(zz'z'')=r(zz')s(z'z'')$, for every $z$, $z'$ and $z''$ in $\phi(S)$. 

Of course, this condition is far from sufficient. In fact, to be able to say anything even moderately interesting about this problem, one should probably specify the kind of processes $Y$ and $Z$ one has in mind.