How do you show from the index notation that the change of frame formula for a metric must involve the transpose?

Let $x^\mu$ and $x^{'\mu}$ be two coordinate systems related by $$dx^{'\mu}~=~S^\mu{}_\nu~ dx^\mu.$$ In index notation the metric in both systems are related by: $$g'_{\rho\sigma}~=~g_{\mu\nu}~(S^{-1})^\mu{}_\rho~(S^{-1})^\nu{}_\sigma.$$

In matrix form this is $$g'~=~(S^{-1})^Tg(S^{-1}).$$

How is it clear from the index notation that the matrix form must involve the transpose matrix?

Repeated indices will be summed throughout. Recall that given any two matrices $A = (A_{ij})$ and $B = (B_{ij})$, the matrix product is a new matrix $AB = (C_{ij})$ defined as follows: \begin{align} C_{ij} = A_{ik}B_{kj} \end{align} In particular, if we think of the first index as the row index and the second index as the column index, then we see that in the matrix product, the column index of the first matrix factor (matrix $A$) is being summed with the row index of the second factor (matrix $B$).

Now, recall that for $A$ given as above, its transpose is defined by $(A^T)_{ij} = A_{ji}$, so we would have \begin{align} (A^TB)_{ij} = (A^T)_{ik}B_{kj} = A_{ki}B_{kj} \end{align} In other words, when we multiply the transpose of a matrix $A$ with another matrix $B$, in index notation this corresponds to summing over the row indices of both factors $A$ and $B$.

Given these observations, and using the standard convention that the left-most index is the row index (regardless of whether it's up or down) and the right-most index is the column index, we see that in the expression \begin{align} (S^{-1})^\mu_{\phantom\mu\rho} g_{\mu\nu}(S^{-1})^\nu_{\phantom\nu\sigma} \end{align} the row index of the first $S^{-1}$ factor is being summed with the row index of $g$; so the first two factors involve the product of $(S^{-1})^T$ and $g$.

joshphysics's answer addresses how to convert between the index and matrix notations. Here's something I use to avoid mistakenly converting it to $(S^{-1}gS^{-1})$, which might happen because the two appreances of $S$ in the index notation look symmetric: notice that the expression

$$g_{\mu\nu}~(S^{-1})^\mu{}_\rho~(S^{-1})^\nu{}_\sigma$$

is unchanged when we swap $\rho$ with $\sigma$, which means that it represents a symmetric tensor. The expression

$$(S^{-1})^Tg(S^{-1})$$

is also symmetric, which we can see by taking the transpose.