Nonholonomic dynamical systems, i.e. systems with nonintegrable constraints, are different both from Hamiltonian systems and from typical dissipative systems. They do not have the Poisson structure and the measure (unlike the former) and, as a rule, conserve the energy (unlike the latter). We study the problem of existence for nonholonomic systems of various tensor invariants, such as integrals of motion, fields of symmetries, the invariant measure, and the Poisson structure. We also consider the relation that exists between various types of dynamical behavior of these systems and the existence of tensor invariants. We show that the classical problems of nonholonomic mechanics, such as the problem of a body rolling on a plane and on a sphere, and that of ball rolling on an arbitrary surface, involve various cases when tensor invariants exist, which determine the entire hierarchy of possible types of dynamical behavior. The extreme cases of this hierarchy are, on one hand, completely integrable systems (according to the Euler--Jacobi theorem), which can have the full set of first integrals and the invariant measure that behave quite regularly, and on the other hand, systems that have neither integrals of motion, nor invariant measure. The latter can display chaotic behavior, which can be either Hamiltonian or dissipative. Besides, we show the existence of a strange attractor in such systems, at certain energy levels in the system's phase space. We also find a number of new integrable cases in these problems of nonholonomic mechanics and a new example of a system, which displays not only typical features of the well- known rattleback model, but some new interesting properties as well.