I know that given a Riemannian manifold $M$ and two closed submanifolds $N_1$ and $N_2$ of it, if one of $N_1$ and $N_2$ is compact, then there exists a geodesic which minimizes the distance between $N_1$ and $N_2$.
Now the question is that if $N_1$ and $N_2$ are compact subsets one can guarantee that there exists a geodesic which minimizes the distance between $N_1$ and $N_2$?
I appreciate any comments in advance!
You need to assume that $M$ is (geodesically) complete for this to be true in general (this is already true for your introductory statement).
Apart from that: yes, that's true. Since both sets are compact and the distance is continuous the distance is realized in two points $p_i \in N_i$ (i.e. $d(N_1, N_2) = d(p_1, p_2)$). Now just join $p_1$ and $p_2$ with a geodesic.