Beamer: Uncover underbrace

One way to do that, is to use the definition of the transparency (15% Text foreground on the background and to avoid the “jumping” use as suggested here the overprint environment.

Though you have to define your term that's \underbraced twice and in my quick hack the transparency color is the one mentioned above, because i didn't find whether i can somehow get that by \usebeamercolor

\documentclass[transparent]{beamer}
\usepackage{amsmath}
\usepackage{cancel}
\begin{document}
    \setbeamercovered{transparent}
    \begin{frame}%
        \begin{overprint}
            \onslide<1>\begin{displaymath}
                \color{normal text.fg!15!normal text.bg}
                \underbrace{\usebeamercolor[fg]{text}foo}_{bar}
            \end{displaymath}
            \onslide<2>\begin{displaymath}
                \underbrace{foo}_{bar}
            \end{displaymath}
        \end{overprint}
    \end{frame}%
\end{document}

And (thanks to @Andrew Stacey) the even shorter version just switching colors using \only (because \color is sensitive to that) would be

\begin{frame}
    \begin{displaymath}
        \color{normal text.fg!15!normal text.bg}
        \only<2->{\color{normal text.fg}}
        \underbrace{\usebeamercolor[fg]{text}foo}_{bar}
    \end{displaymath}
\end{frame}

Here's a solution that just uses \onslide (so that there's no need to know the precise definition of transparency):

\documentclass{beamer}
\setbeamercovered{transparent}
\begin{document}
\begin{frame}
    \begin{displaymath}
        \onslide<2-> \underbrace{ \onslide<1->
        foo
        \onslide<2-> }_{bar} \onslide<1->
        \text{some more stuff for slide 1}
    \end{displaymath}
\end{frame}
\end{document}

Based on Hendrik Vogt's answer, and for my needs, I created these commands to make my life easier:

\newcommand<>{\uncoverubrace}[2]{%
  \onslide#3 \underbrace{ \onslide<1->%
  #1%
  \onslide#3 }_{#2} \onslide<1->%
}
\newcommand<>{\uncoverobrace}[2]{%
  \onslide#3 \overbrace{ \onslide<1->%
  #1%
  \onslide#3 }^{#2} \onslide<1->%
}

Now the use is very simple:

\usepackage{mathtools}
...
\begin{displaymath}
\uncoverubrace<2->{a_i}{\mathclap{\text{$N$ elements}}} =
\frac{
  \uncoverobrace<3->{b_j-b_i}{\mathclap{\text{$2N$ items needed}}}
}{2h}
\end{displaymath}

Room for improvement: allow relative overlay specifications (<+->).