$\def\vec#1{\mathbf{#1}}\def\tr{\mathop{\mathrm{tr}}}$ I'll develop the answer suggested in the comments for the sake of clarity. I'm assuming that you want conditions for $M$ such that $\forall M: \| MN \|_F \geqslant \| M \|_F~$(where $\|\ast\|_F$ is the Frobenius norm).

I will generally consider the squares of the Frobenius norm, as the inequality is preserved under squaring. Consider an operator $M$ with singular value decomposition $$ M = \sum_j s_j \; \vec q_j \vec r_j^\ast \;,$$
where $\vec q_j$ and $\vec r_j$ are the orthonormal sets of left- and right-singular vectors, and where the singular values are a decreasing sequence of non-negative reals, $s_1 \geqslant s_2 \geqslant \cdots \geqslant 0$.
Then the Frobenius norm of $M$ is just the Euclidean norm of the vector $\vec s$ of singular values, by
$$ \| M \|_F^2 \;=\;\tr(M M^\ast) = \tr\left( \sum_j \sum_k s_j s_k \; \vec q_j^{\phantom \ast} \vec r_j^\ast \vec r_k^{\phantom \ast} \vec q_k^\ast \right) = \;\sum_j s_j^2 \;.$$
Consider what happens when we multiply on the left by $M$: the square of the Frobenius norm is
$$\begin{align*} \| MN \|_F^2 \;&=\;\tr(MN N^\ast M^\ast) \;=\;\tr(N^\ast M^\ast MN)
\\\\&= \sum_j \sum_k s_j s_k \tr\left( N^\ast \vec r_j^{\phantom \ast} \vec q_j^\ast \vec q_k^{\phantom \ast} \vec r_k^\ast N \right)
\\\\&= \;\sum_j s_j^2 \tr\left( N^\ast \vec r_j^{\phantom \ast} \vec r_j^\ast N \right)
\\\\&= \;\sum_j s_j^2 \tr\left( \vec r_j^\ast N N^\ast \vec r_j^{\phantom \ast} \right)
\\\\&= \;\sum_j s_j^2 \bigl\| N^\ast \vec r_j^{\phantom \ast} \bigr\|_F^2
\;,\end{align*}$$
using the cyclic property of the trace on the second and second-to-last lines, and the fact that the trace of a scalar is just the scalar itself (which happens in this case to be the inner product of a vector with itself, or the Euclidean-norm-square of that vector).

We want the value on the last line above to be larger than $\| M \|_F^2$ no matter what the right-singular vectors $\vec r_j$ happen to be, or what the singular values $s_j$ are. In particular, it must be larger even if $s_1$ is the only non-zero singular value (that is, even if $M$ is a rank one operator); so we may as well reduce to that special case — we require $\| N^\ast \vec r \|_F \geqslant 1$ for all unit vectors $\vec r$. If you consider the singular value decomposition of $N^\ast$,
$$ N^\ast = \sum_k c_k \; \vec a_k \vec b_k^\ast \;,$$
this means in particular that the smallest singular value $c_n$ must be at least $1$; otherwise, we would have $\| N^\ast \vec b_n \|_F = c_n \| \vec a_n \| < 1$.

We have almost shown what was stated in the comments. Note that we can easily obtain the singular value decomposition of $N$ from that of $N^\ast$:
$$ N = \left( \sum_k c_k\; \vec a_k \vec b_k^\ast \right)^\ast = \sum_k c_k\; \vec b_k \vec a_k^\ast \;;$$
then the singular values of $N$ must also be at least $1$. Also, because all of the singular values of $N$ are positive, it is invertible; and we can easily show
$$ N^{-1} = \sum_k c_k^{-1} \;\vec a_k \vec b_k^\ast \;.$$
Then the maximum singular value of $N^{-1}$ is at most $1$, or equivalently

$$ \Bigl\| N^{-1} \Bigr\|\_\infty \leqslant\; 1\;, $$
where $\| \ast \|_\infty$ is the *uniform norm* on operators:
$$ \| A \|_\infty = \sup\; \Bigl\{ \| A \vec v \| \;:\; \vec v \in \mathop{\mathrm{dom}}(A) \text{ and } \|\vec v\| = 1 \Bigr\}. $$

(For operators on finite-dimensional vector spaces, the supremum can be replaced with a maximum; then the uniform norm is essentially the largest singular value by definition.) This is just another way to formulate the criterion, and (because the uniform norm is a useful operator norm in its own right) possibly the most useful way to present it succinctly. It is easy to see that $N$ being invertible and $\| N^{-1} \|_\infty \leqslant 1$ are both necessary and sufficient conditions: if $N^{-1}$ shrinks all vectors, then $N$ stretches all vectors, and in particular the right-singular vectors of any matrix $M$.

for all $M$, we have $\Vert MN\Vert \geq \Vert M\Vert$?" If so, then I can't see what is wrong with Mikael's answer – Yemon Choi Oct 14 '12 at 22:15