What does the $O^*$ notation mean?
Similarly as $O$ notation which "ignores constant factor", $O^*$ notation "ignores polynomial factor" that is: $f(n) = O^*(g(n))$ if there exists some polynomial $p$ such that $f(n) \leq p(n) g(n)$ for $n$ large enough. This is mainly used to compare functions which are growing exponentially, in which case polynomial factors are less important. 

This notation is not as standard as $O,o,\Omega, \omega$. Sometimes, this notation or $\tilde{O}$, as observed by @Raphael, is used to ignore polylogarithmic factor when people focus on ptime algorithms.