Is it true that if $N/M$ is a normal subgroup of $G/M$ then $N$ is a normal subgroup of $G$ itself?
I would think that not necessarily because I would expect that under conjugation we could get a subgroup of $G$ isomorphic to $N$ but maybe not $N$ it self but a subgroup identical from $N$ except its elements be differing from $N$ by elements of $M$.
However I think the correspondence theorem says that $N$ is normal in $G$ so I am a bit confused is it normal after all?
Yes, this appears to be true. Consider the map $f: G \to (G/M)/(N/M)$ that sends $g$ to its equivalence class mod $M$, and then sends the result to its equivalence class mod $N/M$. That is, this is just the projection map from quotienting by $M$ and then by $(N/M)$.
We argue that $N = \ker f$: thus, $N$ is normal and $G/N$ is isomorphic to $(G/M) / (N/M)$.
To prove it, first let $n \in N$. Then $f(n) = 1$ because $n$ first maps to $n M$ which then maps to $1$ since $(nM) \in (N/M)$.
On the other hand, let $g \in G$, and suppose $f(g) = 1$. Then $gM \in (N/M)$, so $gM = nM$ for some $n \in N$. In particular $g \in gM$, so $g \in nM$, so $g = nm$ for some $m \in M$, and since $M \subseteq N$, $g \in N$.