Table and figure side-by-side with independent captions

Use a floatrow environment of the package of the same name.

\documentclass{article}

\usepackage{floatrow}
% Table float box with bottom caption, box width adjusted to content
\newfloatcommand{capbtabbox}{table}[][\FBwidth]

\usepackage{blindtext}

\begin{document}

\blindtext

\begin{figure}
\begin{floatrow}
\ffigbox{%
  \rule{3cm}{3cm}%
}{%
  \caption{A figure}%
}
\capbtabbox{%
  \begin{tabular}{cc} \hline
  Author & Title \\ \hline
  Knuth & The \TeX book \\
  Lamport & \LaTeX \\ \hline
  \end{tabular}
}{%
  \caption{A table}%
}
\end{floatrow}
\end{figure}

\end{document}

You can use the »caption« package. See code below for an example derived from the package manual.

\documentclass[11pt]{article}
\usepackage[T1]{fontenc}
\usepackage[font=small,labelfont=bf,tableposition=top]{caption}

\DeclareCaptionLabelFormat{andtable}{#1~#2  \&  \tablename~\thetable}

\begin{document}
  \begin{figure}[!ht]
    \centering
    \rule{6.4cm}{3.6cm}
    \qquad
    \begin{tabular}[b]{cc}\hline
      Table head & Table head \\ \hline
      Some values & Some values \\
      Some values & Some values \\
      Some values & Some values \\
      Some values & Some values \\
      Some values & Some values \\
      Some values & Some values \\ \hline
    \end{tabular}
    \captionlistentry[table]{A table beside a figure}
    \captionsetup{labelformat=andtable}
    \caption{A table beside a figure}
  \end{figure}
\end{document}

You will find more details in the manual. This is not exactly what you want, but it would float.

---

---

Supplement:

Another solution that would give the desired output. But this won't float.

\documentclass[11pt,a4paper,english]{article}
\usepackage[T1]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage{babel}
\usepackage[font=small,labelfont=bf]{caption}

\begin{document}
  \begin{minipage}{\textwidth}
  \begin{minipage}[b]{0.49\textwidth}
    \centering
    \rule{6.4cm}{3.6cm}
    \captionof{figure}{A table beside a figure}
  \end{minipage}
  \hfill
  \begin{minipage}[b]{0.49\textwidth}
    \centering
    \begin{tabular}{cc}\hline
      Table head & Table head \\ \hline
        Some values & Some values \\
        Some values & Some values \\
        Some values & Some values \\
        Some values & Some values \\
        Some values & Some values \\
        Some values & Some values \\ \hline
      \end{tabular}
      \captionof{table}{A table beside a figure}
    \end{minipage}
  \end{minipage}
\end{document}

---