This is the default behavior since version 1.5.0 for the casual style variant (the one you pictured), released today. It is using the fontawesome package as stated in another answer, and will load it automatically.
FYI, the new version of moderncv introduces a way to switch between icon sets, i.e.
\moderncvicons{<icon set>}
where <icon set> can be awesome (the one you wants), marvosym (the old ones) or letters (letter icons, used by default in the oldstyle style variant).
Unfortunately, TeX Live 2012 is frozen right now and TeX Live 2013 will only be released on July 1st. So if you want the icons above, you will need to download the newest version of moderncv manually (fontawesome should already be installed on your system, as it was released before the freeze).
You can use anchor=north for each node in the legend. Even better appears to be anchor=base which aligns with the base line of the first line. Since the images have their center on the baseline, we need to shift them somewhat:
\documentclass{standalone}
\usepackage{pgfplots}
\pgfplotsset{compat=1.9}
\begin{document}
\begin{tikzpicture}
\begin{axis}[
legend style={
/tikz/every odd column/.style={yshift=2pt},
/tikz/nodes={text width=25pt,text depth=,anchor=base},
},
legend entries={%
Some long text,Some other long text
},
]
\addplot {x};
\addplot {1+x};
\end{axis}
\end{tikzpicture}
\end{document}
My idea assumes that the images are in the odd columns only.
Note: for some reason, the /tikz/ prefix is mandatory in this context (although it usually isn't).
Best Answer
The added code will lower the three symbols, aligning them with the text.
The symbols are lowered using
\raisebox{<distance>}{<content>}
with a negativedistance
.The vertical position of any symbol can be adjusted using, for example,
will move the symbol phone up a bit to compensate for the taller numbers.