When we prove that "If $M$ is countable, $(P,\le)$ is a partial order and $p\in P$, then there is a $G$ that is $P$-generic over $M$ such that $p\in G$", the axiom of (countable) choice should be used?
If we let $M$ be a transitive set, then we can prove this without using the axiom of countable choice.
But I don't know whether the axiom should be used to prove the general case.
No. The fact that $M$ is countable is already enough, at least assuming that $M$ is a model of [enough] set theory.
The reason here is that it is enough to find a generic filter on the partial order $P\cap M$, which is a countable set. So we can enumerate it, $\{p_n\mid n<\omega\}$ and since $M$ is countable, $\{D\in M\mid D\subseteq P\text{ is dense}\}$ is countable, and we can enumerate it as $\{D_n\mid n<\omega\}$. And now the usual thing works: recursively construct $G$ by taking the least possible condition in $D_n$.
If we do not assume that $M$ is countable, then the axiom of choice might come into play, but there's more finesse to this, and it's best to set this aside for now.