Note that $|G| = |N|[G:N]$.
Suppose $p$ is a prime dividing $|N|$ (I leave it to you to decide what happens when NO prime divides $|N|$). Then since $\gcd(|N|,[G:N]) = 1$, we have that $p\not\mid [G:N]$, that is: $p$ is not a factor of the index of $N$.
Now if $p|o(g)$, then by transitivity of divisibility, we have $p$ divides $|N|$ (since $o(g)$ divides $|N|$ by assumption). So none of the prime factors of $o(g)$ are in $[G:N]$.
Now consider the homomorphism $\pi: G \to G/N$ where $\pi(g) = gN$. We have $|G/N| = [G:N]$, and since $o(gN)|o(g)$ (since if $o(g) = k$, then $(gN)^k = g^kN = eN = N$), a prime factor of $o(gN)$ must divides $o(g)$ and $[G:N]$, and thus $N$ and $[G:N]$.
But by assumption these are co-prime, so we must have $o(gN) = 1$, that is: $gN = N$, whence $g \in N$.
(In all fairness to mich95, this is the same argument spelled out in slightly more elementary terms).