  In nonholonomic mechanics, the presence of constraints in the velocities
breaks the well-under\-stood link between symmetries and first integrals of
holonomic systems, expressed in Noether's Theorem. However there is a known
special class of first integrals of nonholonomic systems generated by vector
fields tangent to the group orbits, called {\it horizontal gauge momenta}, that
suggest that some version of this link should still hold. In this paper we
prove that, under certain conditions on the symmetry Lie group, the
(nonholonomic) momentum map is conserved along the nonholonomic dynamics, thus
extending Noether Theorem to the nonholonomic framework. Our analysis leads to
a constructive method, with fundamental consequences to the integrability of
some nonholonomic systems as well as their hamiltonization. We apply our
results to three paradigmatic examples: the snakeboard, a solid of revolution
rolling without sliding on a plane and a heavy homogeneous ball that rolls
without sliding inside a convex surface of revolution. In particular, for the
snakeboard we show the existence of a new horizontal gauge momentum that
reveals new aspects of its integrability.
