I assume that $G, M, N$ are finite. In this context representations are completely determined by their character, so two $G$-sets $M, N$ have this property if and only if the number of fixed points of any $g \in G$ acting on $M, N$ are always the same. This implies various generalizations of Benjamin Sternberg's answer. For example, the number of orbits of $G$ acting on the subsets ${M \choose k}, {N \choose k}$ of $M, N$ of size $k$ are the same.
Triples $(M, N, G)$ with this property are called Gassmann triples. They were famously used by Sunada to construct pairs of isospectral but not isometric Riemannian manifolds, and can also be used to construct pairs of isospectral (have the same zeta function) but not isomorphic number fields. Ben Webster has a nice pair of blog posts on the subject here and here, and the Wikipedia article has references.