Okay, so I guess I'll summarize all the comments into some anecdotes and make an attempt to add some more insight into the solution here. I'm also going to take a more... narrative approach to history so exact dates and ideas aren't exactly critical to understanding.
At the time Newton was working, he made a bunch of hypothesis. The most famous of which we now consider "laws," although in reality they are still just hypothesis. In particular is the one you pointed out, $F = ma$. We actually know this breaks down in certain regimes and is only valid in what we call "classical mechanics." At the quantum level, all sorts of different things happen and this doesn't hold true any more.
So when Newton came up with these ideas, he was looking at the universe around him. Prior to Newton, most of what was known in physics was discovered by the Greeks and then promptly lost in the Dark Ages. But the Greeks, primarily Aristotle, didn't have a full grasp of the universe around them, although they did propose many ground breaking things like the concept of atoms. Anyway, Aristotle would look at a body like a block on the ground and say that to have a velocity, it had to have a force applied to it. And they could test this -- push a block and it moves, stop pushing and it stops. Experiments verified their hypothesis.
Eventually knowledge of the celestial bodies evolved and planets and moons were discovered and things just didn't quite seem right. What was pushing all those things? Why didn't they stop moving? Where was the big "hand" that was giving them a velocity? This is the famous apple idea -- Newton saw an apple fall from a tree and said "Hey wait a minute, the apple went from rest to moving -- there must be something acting on it!" And then he probably baked himself a nice apple pie and went to sleep.
The moral of the story there is that he realized the universe wasn't accurately described by saying $F = mv$. So he came up with a new hypothesis and started testing it out. And others tested it out. And for the next ~400 years people tested it out. And time and time again, the predictions turned out to be accurate. It became a "law" because it worked! It wasn't until the early 20th century and the introduction of relativity and quantum mechanics that we found places where it didn't really hold true.
You could ask the same question of Einstein and say "Why does $E=mc^2$?" He made a hypothesis and tested the math against what we knew and it seemed to hold. And he made very specific predictions (in this case, about gravitational lensing) which could be measured to verify if his idea was right. It took 15 more years before it was measured (it required a solar eclipse, good weather, avoiding wars, and a hell of a lot of luck).
Now, in some sense, things are a little bit easier. When Newton was working, not all the units existed. He essentially defined the units of force. Now, we take as understood that there are 7 fundamental units (let's just assume SI for now): mass (kilogram), length (meter), brightness (candela), time (second), electrical current (ampere), temperature (kelvin), and discrete quantity (mole). Although I should note, this isn't a guaranteed all-inclusive list -- in 100 years, the AP Physics class could be talking about the lod46 unit for some crazy new fundamental quantity in the universe that is currently unknown.
But for things within those fundamental units, we can construct all kinds of derived quantities and hypothesis for how those quantities are related. Through the simplest approach, we can look at what we expect to matter in the problem based on what we know and start combining what we do know to get them.
For example, we want to know the drag on a body in a flow. We know the surface area of the body, we know the density of the fluid, we know the velocity the body is going, we know the temperature of the fluid, and probably some other things. We also know some things won't matter -- the luminosity of the sun probably doesn't matter, the static electric charge on the balloon a little girl is holding 10 miles from the airport probably doesn't matter, so we can make reasonable assumptions about what to include or exclude. So based on that, we know that drag is some function of all of that, or:
$$ D = f(A, \rho, u, T)$$
We also know drag is a force, so we expect it to have units of Newton (or $kg~m/s^2$). So now we look at how to combine all of those variables to get the units that we want. We see there is no kelvin in our force, so temperature probably doesn't matter. We see that density is the only thing that provides kilograms, so we are pretty confident that drag will depend on that. Our velocity is the only thing that has a time unit, so we know that needs to be there too. That leaves us with the surface area as being possibly duplicate (because we already have a length unit that also comes from our velocity).
We know we need units of $1/s^2$ in our final answer, so we know we should have a $v^2 [m^2/s^2]$ where the resulting units are in brackets. We know we need $kg$ on top, so we have to multiply that by density (which is $kg/m^3$) so we now have $\rho v^2 [kg/s^2/m]$. But now we have a length unit on the bottom and we need one on the top. We still have our surface area, $A [m^2]$ to use and it just so happens that will put a length unit on the top -- $\rho v^2 A [kg m/s^2]$!
So now we have all the variables that seem to make sense for our problem, and we come up with a hypothesis: $D = \rho v^2 A$. Unfortunately, this is a bad hypothesis. All we did is say "these things together give the units we need" but we never said how much each contributes to the total. So a better hypothesis is to say that drag is proportional to those things, or $D \propto \rho v^2 A = c \rho v^2 A$. where we call $c$ a constant of proportionality, which also happens to be unitless.
We now rely on experiments (most commonly) or additional theory/assumptions (less commonly) to determine this constant for us. Just like with Newton's second law, it's not really saying $F = ma$ so much as it's saying $F \propto a$ where the constant of proportionality is this really fundamental thing we call mass.
And for what it's worth, the final expression for drag on a body is:
$$D = \frac{1}{2} c_d A \rho u^2 $$
where $c = 1/2 c_d$. It turns out that theory says a $1/2$ should be part of the constant, and we rely on experiments to determine the drag coefficient $c_d$ for each and every body for which we want to do calculations.
This idea of looking at the important quantities you have and trying to figure out how to combine them is called dimensional analysis which you are likely familiar with from your Chemistry class. When using it to find non-dimensional numbers or looking for "fundamental" ways units combine, it's often called the Buckingham Pi theorem and is used frequently in fluid dynamics and theoretical and data analysis work.
