How do I place captions rotated alongside an image?

This solution uses a tabular (left shifted into the margin slightly) to do all the alignment. It relies on the fact that the images are the same height as width (otherwise one would have to measure the image height).

Two new counters were introduced to allow \labels. The imagecolumn counter will automatically be incremented in each I column. Labels will store whatever you put into \theimagecolumn.

\documentclass{article}
\usepackage{graphicx}
\usepackage{array}
\usepackage{showframe}% debuggin tool

\newcounter{imagerow}[figure]
\newcounter{imagecolumn}[imagerow]
\renewcommand{\theimagecolumn}{Row \arabic{imagerow} Column \arabic{imagecolumn}}

\newcolumntype{I}{>{\refstepcounter{imagecolumn}}{c}<{}}

\newlength{\imagewidth}

\begin{document}
  \begin{figure}
    \def\arraystretch{0}% remove \arraystretch\dp\strutbox from row gap
    \setlength{\imagewidth}{\dimexpr \textwidth - 4\tabcolsep}% each gap takes 2\tabcolsep
    \divide \imagewidth by 3
    \hspace*{\dimexpr -\baselineskip - 2\tabcolsep}% move first column into margin
    \begin{tabular}{@{}cIII@{}}
      \stepcounter{imagerow}\raisebox{0.5\imagewidth}{\rotatebox[origin=c]{90}%
        {\strut Row \theimagerow}} &
      \includegraphics[width=\imagewidth]{example-image-1x1} &
      \includegraphics[width=\imagewidth]{example-image-1x1}\label{example} &
      \includegraphics[width=\imagewidth]{example-image-1x1} \\[2\tabcolsep]% adds gap between rows
      \stepcounter{imagerow}\raisebox{0.5\imagewidth}{\rotatebox[origin=c]{90}%
        {\strut Row \theimagerow}} &
      \includegraphics[width=\imagewidth]{example-image-1x1} &
      \includegraphics[width=\imagewidth]{example-image-1x1} &
      \includegraphics[width=\imagewidth]{example-image-1x1} \\[2\tabcolsep]
        \setcounter{imagecolumn}{0} &% \stepcounter{imagerow} will also work
        Column \arabic{imagecolumn} &
        Column \arabic{imagecolumn} &
        Column \arabic{imagecolumn}
    \end{tabular}
  \end{figure}
Example reference to image at \ref{example}.
\end{document}