Let $P$ be a stochastic $N \times N$ matrix. We consider two independent copies of a Markov process on $\{1,\ldots,N\}$ with transition probabilities given by $P$. Both are assumed to start deterministically at state $1$.
The two processes can be thought of as a single process on $\{1,\ldots,N\}^2$. Is this a markov process? What does the transition matrix look like?
It is indeed a Markov process, on a new state space like you mentioned: $N^2$. What should be the transmission matrix? assuming every step in each chain is independent in the other, the probability of moving from $(n_1, n_2)$ to $(m_1, m_2)$ is the probability of moving in the first chain from $n_1$ to $m_1$, and the same idea in the other chain. By assumption, the requested probability will be ${[P]}^{n_1}_{m_1} \cdot {[P]}^{n_2}_{m_2}$.