Two columns in legend in pgfplots

Simply set the key legend columns=2.

Depending on what you need, you might also be interested in transpose legend and/or reverse legend.

EDIT:

in order to customize the legend's appearance, you can use legend style={<option list>} where <option list> can be any option which applies to a PGF \matrix. All these options can be found in the PGF manual. The one which is necessary here is the column sep key. We have to restrict it to the second column (unless we also want to customize the column separation between images and text).

Here is an example:

\documentclass{standalone}
\usepackage{pgfplots}
\pgfplotsset{compat=1.6}

\begin{document}

\begin{tikzpicture}
    \begin{axis}[
        legend columns=2, 
        legend style={
                    % the /tikz/ prefix is necessary here...
                    % otherwise, it might end-up with `/pgfplots/column 2`
                    % which is not what we want. compare pgfmanual.pdf
            /tikz/column 2/.style={
                column sep=5pt,
            },
        },
    ]
        \addplot {x};
        \addlegendentry{$x$}
        \addplot {x+4};
        \addlegendentry{$x$+4}
    \end{axis}
\end{tikzpicture}

\end{document}