Proper centering with cmidrule and multi- row and column

Use the optional argument of \multirow.

Substituting

\multirow{2}{*}{Sample}

with

\multirow{2}[3]{*}{Sample}

does what you want.

MWE:

\documentclass{article}
\usepackage{booktabs}
\usepackage{multirow}
\begin{document}

\begin{table}[h]\centering
\begin{tabular}{lcccc}
\toprule
\multirow{2}[3]{*}{Sample} & \multicolumn{2}{c}{I} & \multicolumn{2}{c}{II} \\
\cmidrule(lr){2-3} \cmidrule(lr){4-5}
 & A & B & C & D \\
\midrule
S1 & 5 & 8 & 12 & 2 \\
S2 & 6 & 9 & 2 & 6 \\
S3 & 7 & 9 & 5 & 8 \\
S4 & 8 & 9 & 8 & 2 \\
\bottomrule
\end{tabular}
\end{table}

\end{document} 

Output:

Note that I've also changed \cmidrule(l) to \cmidrule(lr) for a better looking table, as suggested by Manuel in the comments.

I had this same problem, and wasn't satisfied with having to guess at the bigstruts argument to \multirow, so I came up with this:

\documentclass{article}
\usepackage{booktabs}
\usepackage{multirow}
\begin{document}

\begin{table}[h]\centering
  \begin{tabular}{lcccc}
    \toprule
    \multirow{2}{*}[-0.5\dimexpr \aboverulesep + \belowrulesep + \cmidrulewidth]{Sample}
    & \multicolumn{2}{c}{I} & \multicolumn{2}{c}{II} \\
    \cmidrule(l){2-3} \cmidrule(l){4-5}
    & A & B & C & D \\
    \midrule
    S1 & 5 & 8 & 12 & 2 \\
    S2 & 6 & 9 & 2 & 6 \\
    S3 & 7 & 9 & 5 & 8 \\
    S4 & 8 & 9 & 8 & 2 \\
    \bottomrule
  \end{tabular}
\end{table}

\end{document}

I think this is correct because multirow is already trying to vertically center two rows' worth of height, but you have to account for the extra space added by \cmidrule, which adds \aboverulesep + \cmidrulewidth + \belowrulesep vertical space. To accomplish that, we tell \multirow to vertically adjust the box downward by half of that \cmidrule space.

If it looks a little off center, I think that's just an illusion because \aboverulesep is smaller than \belowrulesep. I contend that it's "centered" until someone proves me wrong, but you can try -0.5\dimexpr 2\aboverulesep + \cmidrulewidth instead and see if you like the look of that better.

While the above solution just fudges the box down, an alternative is probably to set \bigstrutjot to \dimexpr \aboverulesep + \belowrulesep + \cmidrulewidth and then use \multirow{2}[1]{*}{Sample}. If I understand multirow's documentation, this will actually make the box higher (two rows plus the space added by \cmidrule) rather than just moving the box down. However, in my testing, it yielded the exact same results as the above, and it seems less readable. (Readability being relative, mind you.)