I understand the general idea that a matrix $M$ has some cell $M_{ij}$ that denotes the number of ways we can go from state $i$ to state $j$, but what does $(M^t)_{ij}$ represent? The number of ways to go from $i$ to $j$ after $t$ steps assuming that each state is independent? (by independent I mean if we are in a certain state, the past is completely irrelevant) If this is correct, why is this true / how does this work? Does $M_{ij}$ always represent "the number of ways" or does it represent any kind of transitional quantity?
Also, what does it mean to multiply $M^t$ times a vector $x$ in general? What does a given element of this resulting vector represent?
Your understanding is mostly correct: $(M^t)_{ij}$ represents the number of ways of getting from state $i$ to state $j$ in $t$ steps. Your notion of what you call "independence" is really called the Markov property. One way of stating this is that the only past that matters is the most recent past.
I'm not sure in what situations you would calculate $xM^t$ but you could interpret it as the number of ways in which you can reach state $j$ given the number of ways of getting to state $i$ to begin with.
For example, if:
$$M^3 = \begin{pmatrix} 6 &3 &5 \\ 3 &1 &2 \\ 5 &2 &4 \end{pmatrix}$$
Then the $(i,j)\text{-th}$ entry in
$$ \begin{pmatrix} a_1 & a_2 & a_3 \end{pmatrix} \cdot M^3$$
is the number of ways of getting to state $j$ when there were already $a_i$ ways of being in state $i$.
I'm not sure why you would do this. Transition count matrices are usually taught as an introduction to transition probability matrices, which are much more useful. So to answer you about how this works, I'm not sure how best to explain that. But it's a good idea to check out a few examples and try develop an intuitive explanation for yourself.