"where this principle of relativity from Galileo enters Classical Mechanics? Is it something that already follows trivially from the laws like I'm supposing or it is something that must be added as another axiom of the theory?"
This is tricky to answer, because special principle of relativity (or the Galilei principle of relativity) is a somewhat muddled concept in the literature, because there are actually two or more variants of it. At least there is the original "all motion is relative, there is no special frame" one, and then there is the modern idea by Einstein "form of all basic laws, when formulated the simplest way, is invariant when changing inertial frames". The answer depends on which principle of relativity we are talking about.
Originally, Galilei inferred from examples that motion is relative; in his particular example, that it is impossible to detect smooth motion of a ship from inside a ship, because all processes inside proceed the same way whether the ship is in docks or smoothly sailing the sea.
Then Poincare defined special principle of relativity: all laws of physical phenomena are the same for all observers moving in translatory motion or at rest; so that detecting this motion or rest is impossible for an observer who is in the moving frame but can only study physical phenomena inside the frame (looking outside is not allowed).
Thus the core of the idea is that it is impossible to detect motion with respect to absolute space (or some unique universal frame of reference). Let us formulate it here this way:
Physical processes in a mechanical system occur the same way, whether the system is at rest, or moving rectilinearly with respect to the absolute space (or any preselected inertial reference frame). (*)
Newton's laws are compatible with the PR, but they do not require it. Neither can be derived from the other. One can have a universe where :
- Newton's laws are valid and PR is valid; for example, system of particles with only inter-particle forces that depend only on differences of position, the set of equations
$$
\mathbf F_{-1}( \text{\{}\mathbf r_1-\mathbf r_k\text{\}}_k)=m\ddot{\mathbf r}_1
$$
$$
\mathbf F_{-2}( \text{\{}\mathbf r_2-\mathbf r_k\text{\}}_k)=m\ddot{\mathbf r}_2
$$
$$
..
$$
- Newton's laws are valid and PR is invalid; for example a universe with a preferred frame of reference which generates friction force $-k\mathbf v$ for any body that moves with velocity $\mathbf v$ with respect to this frame. The set of equations (valid in any frame) is
$$
-k_1(\mathbf v_1 - \mathbf v_f)= m\ddot{\mathbf r}_1
$$
$$
-k_2(\mathbf v_2 - \mathbf v_f)= m\ddot{\mathbf r}_2
$$
$$
..
$$
where $\mathbf v_f$ is velocity of the preferred frame. Similar example would be universe with a global magnetic force $(\mathbf v - \mathbf v_f)\times \mathbf C$ where $\mathbf C$ is some position independent vector. The observer can tell he is moving based on the effects of these frame-defined forces.
So with principle of relativity defined as (*), it is really more a statement about our universe which Newton's laws (the three laws without gravitation) do not capture.
But there is another meaning of the principle of relativity alluded to above; the Einstein statement:
If a system of coordinates K is chosen so that, in relation to it, physical laws hold good in their simplest form, the same laws hold good in relation to any other system of coordinates K' moving in uniform translation relatively to K. (**)
This is very often interpreted as restriction on the possible laws of motion relating basic physical quantities $Q_1,Q_2,...$ to each other and to space and time.
But this form of the principle of relativity is quite vague/useless on its own. It is easy to show that all above toy universes obey this variant of PR; including those with a preferred frame. So this statement is too general: it allows universes with preferred frames.
Does this statement follow from Newton's laws? If we include the Galilei transformation, then probably yes; it is hard to imagine a law relating particle masses, positions, velocities and accelerations which would not obey a requirement this general. By introducing additional variables (velocity of the preferred frame) one can always make the form of the equations be the same in all frames.
For example, this is the case even for Maxwell's equations for fields, when using the Galilei transformation; one can find the general Galilei-invariant form of the equations featuring velocity of the ether (which simplifies to standard Maxwell's equations in the ether frame). Of course this conformance to principle of relativity (**), or "Galilei invariance" of the equations, wasn't any proof of the form of the equations being correct. Galilei invariance requires either infinite or frame dependent speed of light, which was disproved by experiments.