Minipages and captionsetup to the rescue
@Ulrike Fischer's answer is a good start. By placing the sub-figures exactly next to each-other you can get each colorbox to touch the next one.
This, however, results in captions which may be too close to each other. To address this, I've wrapped each subfloat in a minipage and added \captionsetup{width=0.95\textwidth} to constrain the width of the sub-captions. It's also important to be sure that the contents of each colorbox is fully as wide as the space needed, so I've used yet another minipage.
For example:
\begin{figure}
\centering
\begin{minipage}{0.32\linewidth}
\captionsetup{width=0.95\textwidth}
\subfloat[A long caption about cherries that spans two lines]{
\colorbox{black}{
\begin{minipage}{\linewidth}
\centering
{\color{red}\rule{0.8\textwidth}{90pt}}
\end{minipage}
}
}
\end{minipage}
\begin{minipage}{0.32\linewidth}
\captionsetup{width=0.95\textwidth}
\subfloat[A long caption about oranges that spans two lines]{
\colorbox{black}{
\begin{minipage}{\linewidth}
\centering
{\color{orange}\rule{0.8\textwidth}{90pt}}
\end{minipage}
}
}
\end{minipage}
\begin{minipage}{0.32\linewidth}
\captionsetup{width=0.95\textwidth}
\subfloat[A long caption about apples that spans two lines]{
\colorbox{black}{
\begin{minipage}{\linewidth}
\centering
{\color{green}\rule{0.8\textwidth}{90pt}}
\end{minipage}
}
}
\end{minipage}
\caption{Some fruits, with a black background to help with contrast.}
\end{figure}
Results in:

Improve this!
I tend to overuse minipages. Please post a better answer and I'll accept it.