How to show two groups of equations side by side: one implies the other?

Here is another approach, with some braces added to "combine" the separate equation sets. Of course, these can be removed if needed. Each equation set is aligned along the binary relations in an rcl (right-center-left) fashion with the appropriate spacing.

\documentclass{article}
\usepackage{amsmath}% http://ctan.org/pkg/amsmath
\begin{document}
\begin{align*}
  \left.\begin{array}{r@{\mskip\thickmuskip}l}
    \nabla f(x) -\mu X^{-1} e + A(x) \lambda - z &= 0, \\
    c(x) &= 0, \\
    -\mu X^{-1} e + z &= 0, \\
    x &> 0 \\
    z &> 0
  \end{array} \right\}
  \quad \implies \quad
  \left\{\begin{array}{r@{\mskip\thickmuskip}l}
    \nabla f(x) + A(x) \lambda - 2z &= 0, \\
    c(x) &= 0, \\
    -\mu X^{-1} e + z &= 0, \\
    x &> 0 \\
    z &> 0
  \end{array}\right.
\end{align*}
\end{document}

The error message actually tells you what to do: use the {aligned} environment. This is a sub-environment that can be used inside of any kind of math, that works like {align} except that it takes up only the minimum width necessary (rather than the whole line). You want to do something like:

\[
\begin{aligned}
\nabla f(x) -\mu X^{-1} e + A(x) \lambda - z = 0, 
\\ c(x) = 0, 
\\ -\mu X^{-1} e + z = 0, 
\\ x > 0
\\ z > 0
\end{aligned} 
\quad \implies \quad
\begin{aligned}
\nabla f(x) + A(x) \lambda - 2z = 0, 
\\ c(x) = 0, 
\\ -\mu X^{-1} e + z = 0, 
\\ x > 0
\\ z > 0
\\
\end{aligned}
\]

I took the liberty of making a few other changes. First, you should not use $$...$$, but rather \[...\], which is redefined to check better for errors and behave more like the other amsmath environments. Second, you can use \implies rather than the literally but uninformatively-named \Longrightarrow. Third, I didn't do this, but you may want some alignment tabs in there.

You can also use a table for this purpose. You just have to put an {aligned} inside math in each cell:

\begin{tabular}{ccc}
$\begin{aligned}
\nabla f(x) -\mu X^{-1} e + A(x) \lambda - z = 0, 
\\ c(x) = 0, 
\\ -\mu X^{-1} e + z = 0, 
\\ x > 0
\\ z > 0
\end{aligned}$ 
&$\quad \implies \quad$&
$\begin{aligned}
\nabla f(x) + A(x) \lambda - 2z = 0, 
\\ c(x) = 0, 
\\ -\mu X^{-1} e + z = 0, 
\\ x > 0
\\ z > 0
\\
\end{aligned}$
\end{tabular}

This works because {aligned} can go into any math environment. You can even embed it in text inside a paragraph, though that is quite ugly.

The following code may be the least-invasive adjustment of the original question. It places the two align* structures into minipages and inserts & characters to tell latex where to align the individual equations on.

\documentclass[a4paper]{article}
\usepackage{amsmath}
\begin{document}
\noindent
\begin{minipage}{0.45\textwidth}
  \begin{align*}
    \nabla f(x) -\mu X^{-1} e + A(x) \lambda - z &= 0,\\ 
    c(x) &= 0,\\ 
    -\mu X^{-1} e + z &= 0,\\ 
    x &> 0\\ 
    z &> 0
  \end{align*} 
\end{minipage}
$\quad \Longrightarrow \quad$
\begin{minipage}{0.35\textwidth}
  \begin{align*}
    \nabla f(x) + A(x) \lambda - 2z &= 0,\\ 
    c(x) &= 0,\\ 
    -\mu X^{-1} e + z &= 0,\\ 
    x &> 0\\ 
    z &> 0
  \end{align*}
\end{minipage}
\end{document}

The only thing that's not quite right is the vertical positioning of the \Longrightarrow. I suppose this could be "fixed" by placing it into a minipage/gather system of its own. However, I actually prefer the look of @Werner's suggested solution.