Galilean Relativity is already included in Newton's Laws? Usually I see an inertial reference frame being defined as a reference frame in which Newton's first and second laws holds. That means that if a particle is at rest, it stays at rest unless some external force acts upon it and that if it is in uniform motion on a straight line it stays that way unless some external force changes that.
Most books I've seem until today after defining one inertial frame that way says that Newton's laws are to valid on inertial frames. That is, they are laws, they are supposed to hold. Is not something like if they hold, it is an affirmation: "they do hold when we work on inertial reference frames".
Now, when reading about Special Relativity, some books says that prior to Einstein there was one "principle of relativity" that could be stated as follows:

The laws of Mechanics are invariant in every inertial reference frame

and that this is the result of Galileo's discussion about Salviatti's ship. I'm having a hard time with this because of the following line of thought:
If Newton's laws do hold on inertial reference frames by the definition of inertial reference frames and by the statement of the laws themselves, why this principle is hanging arround anyway? I mean, it seems to me like something automatic from Newton's laws already.
My question is then: "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?"
 A: Galilean relativity does not automatically hold in Newtonian mechanics.  You are correct that Newton's first two laws appear at first sight to be invariant under galilean transformations, but a galilean transformation only transforms spatial coordinates,they don't actually tell you how forces transform.
If your force laws just has forces that depend only on relative position and relative velocity, then your force law is galilean relativistic in combination with the first and second laws.  Your force law could also depend on galilean invariant scalars such as mass or time, which is where the whole thing gets rather problematic.  
To be a relativistic theory, all the laws (including the laws that spell out the forces, such as newton's law of universal gravitation) need to have the exact same form in every single inertial frame.  Basically, if you can write down your laws without first asking which of the many equivalent frames you are in, then you are fine.  If you can't, then you are not a relativistic theory.
A: 
"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.
A: Newton's second law in one dimension for a conservative force(so that there exists a potential energy function) reads : m*d^2 x/dt^2 = -dV(x)/dx ...(1)
If you do a coordinate transformation such as x'=x-vt, where v is some constant,
d^2x/dt=d^2(x'+vt)/dt
and d/dx= d/d(x'+vt),
So (1) transforms as m*d^2 (x'+vt)/dt^2 = -dV(x'+vt)/d(x'+vt).
This looks trivial, but the effect is of rescaling the position coordinates as a function of time, and the nature of the statement of Newton's second law is still preserved.
Another way:
(This was Newton's second law in its original form)
m*d^2x/dt^2=dp/dt
with the transformation
x'=x-vt
dx'/dt=dx/dt => mdx'/dt=mdx/dt = p=p'
=> dp'/dt=m*(d^2x'/dt^2)
This shows Newton's second law is invariant under Galilean transformations.
P.S: I had too much coffee and too little sleep last night while perusing through lecture notes on special relativity and callously answering this question. Finally got a chance to edit the answer.
