Uncover a multiline equation with beamer

You shouldn't use \onlys for exclusive material, but the overprint environment together with \onslide. It ensures that the required size is reserved on any of the slides and therefore avoids most issues with jumping text:

\documentclass{beamer}
\usepackage{amsmath}
\usepackage{cancel}
\begin{document}

\begin{frame}%
    \begin{overprint}
        \onslide<1>
    \begin{multline*}
        S(1,\dots,s) = \underbrace{\sum_{m=1}^{m_t} (-1)^{m+1} \sum_{i_1<\dots<i_m} I(i_1,\dots,i_m)}_{\text{entropy estimate with correlation order}\, m_t} \\
        + \underbrace{\sum_{m=m_t+1}^{s} (-1)^{m+1} \sum_{i_1<\dots<i_m} I(i_1,\dots,i_m)}_{\text{correlations of order higher than}\, m_t} 
    \end{multline*}
        \onslide<2>
    \begin{multline*}
        S(1,\dots,s) = \underbrace{\sum_{m=1}^{m_t} (-1)^{m+1} \sum_{i_1<\dots<i_m} I(i_1,\dots,i_m)}_{\text{entropy estimate with correlation order}\, m_t} \\
        \xcancel{+ \underbrace{\sum_{m=m_t+1}^{s} (-1)^{m+1} \sum_{i_1<\dots<i_m} I(i_1,\dots,i_m)}_{\text{correlations of order higher than}\, m_t} }
    \end{multline*}
    \end{overprint}
\end{frame}%

\end{document}

This should answer your question about how to uncover multiline equations within beamer. However, the \xcancel macro still causes the second line to jump up, which is a different problem.

I must admit that I hate typing out stuff more than once, so I don't like either solution so far presented! So here's a variation on Hendrik's solution that works by making the \xxcancel command overlay-aware.

\documentclass{beamer}
\usepackage{amsmath}
\usepackage{cancel}
\newcommand<>{\xxcancel}[1]{\alt#2{\xcancel{#1}\vphantom{#1}}{#1}}
\begin{document}

\begin{frame}
    \begin{multline*}
        S(1,\dots,s) = \underbrace{\sum_{m=1}^{m_t} (-1)^{m+1} \sum_{i_1<\dots<i_m} I(i_1,\dots,i_m)}_{\text{entropy estimate with correlation order}\, m_t} \\
        \xxcancel<2->{{} + \underbrace{\sum_{m=m_t+1}^{s} (-1)^{m+1} \sum_{i_1<\dots<i_m} I(i_1,\dots,i_m)}_{\text{correlations of order higher than}\, m_t} }
    \end{multline*}
\end{frame}

\end{document}

Martin essentially gave you what you need. Here's how you can prevent the second line from jumping up:

\documentclass{beamer}
\usepackage{amsmath}
\usepackage{cancel}
\newcommand\xxcancel[1]{\xcancel{#1}\vphantom{#1}}
\begin{document}

\begin{frame}
    \begin{overprint}
        \onslide<1>
    \begin{multline*}
        S(1,\dots,s) = \underbrace{\sum_{m=1}^{m_t} (-1)^{m+1} \sum_{i_1<\dots<i_m} I(i_1,\dots,i_m)}_{\text{entropy estimate with correlation order}\, m_t} \\
        + \underbrace{\sum_{m=m_t+1}^{s} (-1)^{m+1} \sum_{i_1<\dots<i_m} I(i_1,\dots,i_m)}_{\text{correlations of order higher than}\, m_t}
    \end{multline*}
        \onslide<2>
    \begin{multline*}
        S(1,\dots,s) = \underbrace{\sum_{m=1}^{m_t} (-1)^{m+1} \sum_{i_1<\dots<i_m} I(i_1,\dots,i_m)}_{\text{entropy estimate with correlation order}\, m_t} \\
        \xxcancel{{} + \underbrace{\sum_{m=m_t+1}^{s} (-1)^{m+1} \sum_{i_1<\dots<i_m} I(i_1,\dots,i_m)}_{\text{correlations of order higher than}\, m_t} }
    \end{multline*}
    \end{overprint}
\end{frame}

\end{document}

Making the second line not jump revealed that the + in the second line moved; to prevent this, I added {} in front of it.