Non-deterministic evolution means that there are aspects to the system's behavior which are not determined by initial conditions. This is the case in the standard formulation of quantum mechanics, where measurements induce probabilistic changes in the state of the system being measured.

Newtonian mechanics does not have this feature. If you know the state of the system at one moment, then you can calculate the state of the system at the next moment to an arbitrary degree of accuracy. Contrast this with quantum mechanics, in which there is no way to know what state the system will occupy after a measurement, regardless of how well you know the state before the measurement.

The fact that classical physics is formulated via a second-order differential equation (i.e. Newton's 2nd law) with no stochastic elements means that determinism is essentially baked-in to the formalism.

This is to be contrasted with integrability, of which there are several notions. The particular sense in which I mean is Liouville integrability, which essentially means that for a given set of initial conditions, the evolution of the system is completely determined by the conserved quantities (such as energy, momentum, etc).