How to put two figures side by side in a two-column document

This should do:

\begin{figure*}
\centering
\begin{minipage}[b]{.4\textwidth}
<Code for the first figure>
\caption{Caption}\label{label-a}
\end{minipage}\qquad
\begin{minipage}[b]{.4\textwidth}
<Code for the second figure>
\caption{Caption}\label{label-b}
\end{minipage}
\end{figure*}

I used subfigure package:

\begin{figure*}[htp]
  \centering
  \subfigure[random caption 1]{\includegraphics[scale=0.38]{image1}}\quad
  \subfigure[random caption 2]{\includegraphics[scale=0.38]{image2}}
\end{figure*}

Worked flawlessly :)