Table and Figure side-by-side with Table caption above, Figure caption below

If you want them vertically centered, you can use \CenterFloatBoxes, as in the following example:

\documentclass{article}
\usepackage{floatrow}
\usepackage[demo]{graphicx}

\begin{document}

\begin{figure}
\CenterFloatBoxes
\begin{floatrow}
\ffigbox
  {\includegraphics{image}}
  {\caption{A caption for a figure in a figure and a table side by side}\label{fig:test}}
\killfloatstyle
\ttabbox
  {\begin{tabular}{ll}
    \hline
    column1a & column2a \\
    column1b & column2b \\
    column1c & column2c \\
    \hline
  \end{tabular}
  }
  {\caption{A caption for a table in a figure and a table side by side}\label{tab:test}}
\end{floatrow}
\end{figure}

\end{document}

There's also \TopFloatBoxes for alignment at the top and \BottomFloatBoxes, for alignment at the bottom.

The demo option for graphicx simply replaces actual figures with black rectangles; do not use that option in your actual document.

Another solution, using package capt-of and parboxes:

\documentclass{article}
\usepackage{lipsum}
\usepackage{capt-of}
\begin{document}
\thispagestyle{empty}

\lipsum[1]

\begin{figure}
\parbox[t]{4cm}{\null
  \centering
  \rule{3cm}{3cm}%
  \captionof{figure}{A figure}%
}
\parbox[t]{8cm}{\null
\centering
  \vskip-\abovecaptionskip
  \captionof{table}[t]{A table}%
  \vskip\abovecaptionskip
  \begin{tabular}{cc} \hline
  Author & Title \\ \hline
  Knuth & The \TeX book \\
  Lamport & \LaTeX \\ \hline
  Knuth & The \TeX book \\
  Lamport & \LaTeX \\ \hline
  Knuth & The \TeX book \\
  Lamport & \LaTeX \\ \hline
  \end{tabular}
}
\end{figure}
\end{document}