How do formulas get figured out? Many of the formulas I learn in school are derived from more basic formulas — as long you your math is right and assuming the more basic formulas you used are correct, you are bound to get to a correct result... But how do people 'invent' the elementary formulas, like $F=ma$; how can you be sure that that's really the right equation for force? 
 A: The way in which formulas are figured out is through a process which is difficult to describe, because it only happens once per formula, and it is different when the formula can be deduced in some way, vs when it is a purely new relation between quantities which have not been related before.
The fundamental laws of a new regime of physics is never determined purely empirically, it always requires a principle of some sort, in addition to the empirical data, which serves to suggest empirical laws, and to weed out false theories. One of the best examples of a physical argument which produces a new equation is Einstein's argument for $E=mc^2$, described in my answer to this question: Did Einstein prove $E=mc^2$ correctly?
The most important tools which physicists have are the symmetry principles, these can be used to deduce many classical relations. But these are not enough, and there is no general way to describe how to reason about physics to derive new laws--- it must be learned through examples. There are many illuminating examples, but perhaps the best is Heisenberg's 1925 derivation of quantum mechanics. I find this one to be most strange, the most insightful, and requiring the greatest leaps of imagination. It is described on the Wikipedia page for Matrix Mechanics.
The equation you give is not the best example, because you can always say that it is the definition of force. This is not correct, because the force is implicitly assumed to be a physical property of the configuration of the particles, not of the particular particle trajectory, but in order to get rid of the circularity completely, let us assume you know statics, so that you have Archimedes definition of force.
Archimedes demonstrates that you can think of gravity as producing a force on a lever proportional to the mass. Then you know from Galileo's experiments that the acceleration is constant in gravity, and you know from Galileo's arguments that there is a principle of Galilean relativity. You deduce that the force should be proportional to the acceleration, which is invariant under Galilean boosts, and because all the acceleration is at the same rate, that the Archimedes notion of gravitational mass is also the notion of inertial mass in F=ma. Something like this is probably what was going through the heads of the 17th century physicists. It is hard to tell, because F=ma was appreciated by everyone in Newton's time, not just by Newton.
A: They are figured out based on their ability to "economize thought," as Ernst Mach would say. To "economize thought" means to succinctly summarize the results of physical experiments or observations. Since there are many ways of "saving the phenomena" of experiments or observations, there are also many theories and thus many corresponding physics formulae.
For example, consider the following three theories of gravity applied to planetary motion:


*

*epicyclic theory

*Newton's $F\propto1/r^2$ theory

*Einstein's theory of General Relativity (GR)


All three of these theories can explain, within certain limits, a given set of observations of the motions of the planets, but they all use completely different mathematical formulae:


*

*The epicyclic theory basically uses a complex Fourier series (cf. this).

*Newton's theory uses a simple algebraic equation.

*GR uses tensors.


Newton thought that his universal theory of gravitation, $F=Gm_1m_2r^{-2}$, was uniquely, exactly, and logically deduced from Kepler's observations, but this clearly is false because Kepler's observations showed perturbations from a perfect $1/r^2$ law due to the solar system being comprised of many masses. It is also false because, e.g., Einstein's GR theory superseded Newton's theory of gravitation.
Thus, one physics theory (e.g., $p=mv$) is not more logically correct than another (e.g., $p=m+v$), although one might certainly be better at summarizing the results of experiments and observations than another.
Physics formulae do not derive from mathematics like a geometric proof derives from Euclid's axioms. Physics formulae derive from observations and experiment; mathematics does not force a physics formula to be a certain way.
For an excellent book on this whole topic, see The Aim & Structure of Physical Theory by the French physicist, historian, and philosopher of physics, Pierre Duhem.
