Lefaroundabout's comment is important. While we are typically taught that we use science to know things, that is not actually a correct statement. Science is a very powerful tool for creating models that can be used to create educated predictions about how a system will behave, and it is founded on the idea of falsifiable hypotheses, but that doesn't mean we're never wrong. It just means it's possible to disprove our hypotheses.
Your example of making the velocities add is a great example. It's terribly intuitive that velocities add together. If I'm on a train, and I throw the baseball, an observe on the ground sees the baseball hurtling through the air at the train's speed plus the speed of my throw. It would be very natural to assume that light behaves the same way. In fact, I think most people believe this is how light works until they are told otherwise by a science teacher.
Now let's bring in Maxwell's equations. Maxwell's equations do a remarkably good job of predicting how electricity and magnetism behave. You can try to falsify them by building oddly designed experiments to isolate magnetic monopoles and so forth, but we found his laws simply hold up well (at least all the way up to Quantum Mechanics, which is its own beast, and its own story). After a lot of testing, the scientific community came to a consensus that Maxwell's equations are pretty darn reliable. I can't say "they knew his equations were true," because that would be an overstatement, but their confidence was very high.
However, there's a quirk. Maxwell's equations predict a "speed of light." But if you go back to our baseball example, we see that the baseball is going at different speeds in different inertial frames. While I ride on the train at a constant velocity, I am viewing the world from an inertial frame, and I see the ball at one speed. While you are on the ground, standing still, you are viewing the world from an inertial frame, and you see the ball at a different speed. Maxwell's equations simply don't have any room for that. They just say "light has a fixed speed," leaving scientists to ponder what's up with that.
One intuitive approach is to assume the light is traveling through a medium, and the speed of light is with respect to that medium. This is intuitive when you look at effects like drag on a baseball. The drag forces on a baseball aren't dependent on how fast it's traveling with respect to me or you, it's how fast it's traveling with respect to the wind. It was theorized that light might travel in a so called the "luminiferous aether," just like our baseball travels through the air. This solves the conundrum of Maxwell's equations: the "speed of light" is the speed of light with respect to the aether.
So this was a reasonable hypothesis. Just like your "velocities add" hypothesis, it lead to natural ways of thinking about light. Of course, this being a scientific hypothesis, it was designed to be falsifiable. If one could demonstrate that light's movement did not act like there was some privileged reference frame (the frame of the aether), then one would be able to refute this hypothesis. And they did.
The most famous experiment falsifying the aether theories was the Michaelson–Morley experiment. Through clever use of interferometry, they were able to compare the speeds of light going in the direction of the Earth's orbit around the sun versus going across it. Their goal was to determine if the aether was stationary, or if it was somehow "dragged" along by massive objects like the Earth (like how air forms drafts behind a large vehicle). They found, curiously enough, that there was no detectable difference in the speed of light in the two directions. If indeed the aether existed (which they believed at the time), it was so tied to the movement of the earth that we couldn't discern it. It's like you were drafting behind a large vehicle, and instead of feeling the wind pull you forward, it felt more like you were encased in concrete and being dragged forcefully along!
Many other experiments also found results like this, which made aether theories start to seem very unreliable. They just called for too much "hand waving." From this, we developed the Lorentz boosts, which were modifications to Maxwell's equations which were very effective at predicting the results of experiments like these, but made the equations terribly ugly. The beauty of Maxwell's equations vanished under the Lorenz transformations.
So now enter Einstein, making his assumption that the speed of light must be the same in all reference frames. I agree with your original opinion that it's a strange thing to just assume. But it was brilliant. When he was done with the math, the ugly Lorenz boosts that defiled Maxwell's equations were neatly tucked away into this assumption that the speed of light was the same in all reference frames. It did a very good job of cleaning up a lot of ugliness in the theories. People liked it.
More than being liked, it was scientific: it was falsifiable. If we ever found two inertial frames which had different speeds of light, or if we found out that time dilation did not occur, it would have falsified Einstein's theories, and we probably wouldn't revere him as we do today. However, in hundreds (if not thousands) of experiments, we have found that Einstein's theory is extraordinarily good at predicting some really awkward and unintuitive effects.
So thus, we justify his assumption that the speed of light is the same in all inertial frames after the fact. We have found that the results of this assumption are tremendously useful and effective. At the time, the justification was that it was an elegant solution to a very difficult problem, and it produced new falsifiable hypotheses to test (like any good scientific theory does).
Best Answer
It doesn't need to since it is a guiding principle, a razor. It is a statement about the nature of physical law.
Put another way, on this principle, an alleged 'physical law' that isn't invariant under inertial coordinate transformations is not a genuine physical law.
Consider, for example
$$\vec F = m \vec a $$
If this equation holds in one coordinate system, it holds in all the coordinate systems related to this one by a Galilean transformation. Thus, it is invariant (unchanged) by this transformation.