Here's another version which defines a new arrow, \xrighttransarrow (maybe there's a better name ...). This is an extensible arrow modelled on the definition of \xrightarrow which makes the * a part of the arrow, rather than a decoration to be added on afterwards. There's a bit of jiggery-pokery to get the spacing right: the * has to be ignored as far as the placement of the \tau is concerned, but then it has to be taken into account when positioning the arrow with its surrounding text. I may well have messed up those bits as I'm no expert on lengths. It's also possible that it would go wrong in different maths styles.
Here's the code:
\documentclass{article}
\usepackage{amsmath}
\makeatletter
\newdimen\arrow@ht
\setbox\@tempboxa\hbox{\(\rightarrow\)}
\arrow@ht\ht\@tempboxa
\newdimen\star@wd
\setbox\@tempboxa\hbox{\(\scriptstyle *\)}
\star@wd\wd\@tempboxa
\def\righttransarrowfill@{\arrowfill@\relbar\relbar{\raisebox{0pt}[\arrow@ht][0pt]{\(\rightarrow^*\hskip-\star@wd\)}}}
\setbox\@tempboxa\hbox{\(\rightarrow\)}
\arrow@ht\ht\@tempboxa
\newcommand{\xrighttransarrow}[2][]{\ext@arrow 0359\righttransarrowfill@{#1}{#2}\hskip\star@wd}
\makeatother
\begin{document}
\(
a\rightarrow^* b
a\xrightarrow\tau^* b
a\xrightarrow{\raisebox{0pt}[0pt][0pt]{\(\scriptstyle\tau\)}}^* b
a \xrighttransarrow\tau b
\)
\end{document}
Here's the result (note that there's also another \raisebox solution in the middle there):

\documentclassand the appropriate packages so that those trying to help don't have to recreate it. – Peter Grill Nov 22 '11 at 10:59