Here's the relevant quotation from Landau and Lifgarbagez. It's from chapter 2 of "Mechanics".
"During the motion of a mechanical system, the 2s quantities q_i and \dot q_i (i=1,2,...,s) which specify the state of the system vary with time. There exist, however, functions of these quantities whose values remain constant during the motion, and depend only on the initial conditions. Such functions are called integrals of the motion.
The number of independent integrals of the motion for a closed mechanical system with s degrees of freedom is 2s-1. This is evident from the following simple arguments. The general solution of the equations of motion contains 2s arbitrary constants (see the discussion following equation (2.6)). Since the equations of motion for a closed system do not involve time explicitly, the choice of the origin of time is entirely arbitrary, and one of the arbitrary constants in the solution of the equations can always be taken as an additive constant t_0 in the time. Eliminating t + t_0 from the 2s functions
q_i = q_i ( t + t_0 , C_1 , C_2 , ..., C_{2s-1}) , \hspace {3 mm} \dot q_i = \dot q_i (t + t_0 , C_1 , C_2 , ..., C_{2s-1} ),
we can express the 2s-1 arbitrary constants C_1 , C_2 , ..., C_{2s-1} as functions of q and \dot q, and these functions will be integrals of the motion."
Equation 2.6 is
<br />
\frac {d}{dt} ( \frac {\partial L}{\partial \dot q_i}) - \frac {\partial L}{\partial q_i}=0 \hspace {10 mm} (i=1,2,...,s)<br />
and the following discussion is
"Mathematically, the equations (2.6) constitute a set of s second-order equations for s unknown functions q_i (t). The general solution contains 2s arbitrary constants. To determine these constants and thereby to define uniquely the motion of the system, it is necessary to know the initial conditions which specify the state of the system at a given instant, for example the inital values of all the coordinates and velocities."
So I guess finding the conserved quantities in a system involves both finding the solutions to the Lagrange equations, and then rearranging them in such a way that all the initial value constants are functions of q's and \dot q's.