Why in Newton's law of gravity, we do $M_1 \times M_2$ and not $M_1 + M_2$? In Newton's law of gravity $$F=\frac{G M_1 \cdot M_2}{r^2}$$ we do the product $M_1 \times M_2$ and not the sum $M_1 + M_2$. Why's that so?
 A: Imagine the force between a star and a planet or moon.
If you doubled the mass of the smaller body then the gravity between them should double.
If they merely added then doubling the mass of a moon which is millions of times smaller than a star would have no real effect on the force between them. 
A: As dulciepercy notes, the single most important reason to believe that the gravitational force between two bodies is (at least approximately) proportional to the product of their masses is that it agrees with experimental results.  We can, in fact, measure the gravitational force between two objects, and the results indeed show that the force scales with the product of their masses.  (In fact, a much simpler experiment is enough to show that.)
That said, one reason why we should expect this rule to hold, even a priori, is that everyday experience tells us that gravity does not care how we divide the world around us into distinct "objects".  In particular, if we have a single massive object, we do not expect the total gravitational effect it has on other things around it to change just because we decide to divide it into two objects of half the original mass, whether just conceptually in our heads, or by actually physically cutting it in half.
In particular, let's do a simple though experiment.  Assume that we have two objects, whose masses we may, for simplicity, assume to be $N_1$ and $N_2$ times some small unit mass $m_0$.  (For example, we could think of two lumps of pure metal, where $m_0$ is the mass of one atom of the metal, and $N_1$ and $N_2$ are the number of atoms in each lump.)
Let $F$ be the total gravitational force between the two objects at distance $r$ from each other (where we'll assume, again for simplicity, that $r$ is much greater than the maximum diameter of either individual object, so that we need not consider the effects of their shape).  To be consistent with logic and everyday experience, we expect that $F$ should be the same regardless of whether we consider the two object as single bodies with masses $M_1 = N_1 \cdot m_0$ and $M_2 = N_2 \cdot m_0$, or as collections of $N_1$ and $N_2$ atoms with mass $m_0$ each.
Now, let $f_0$ be the gravitational force between two atoms of mass $m_0$ at the distance $r$.  (It doesn't really matter how that force might depend on $m_0$; we can just take it as a given for now.)  Now, since every pair of atoms gravitationally attracts each other with that same force, the total force between two collections, of $N_1$ and $N_2$ atoms each, must be the sum of the forces between each of the pairs of atoms:
$$\begin{aligned}
F &= \sum_{n_1 = 1}^{N_1} \sum_{n_2 = 1}^{N_2} f_0 \\
&= \sum_{n_1 = 1}^{N_1} N_2 \cdot f_0 \\
&= N_1 \cdot N_2 \cdot f_0 
\end{aligned}$$
Thus, the total gravitational force between the two objects, viewed as collections of atoms of constant mass, must be proportional to the product of the numbers of atoms in each object.  But, since the mass of each object is also proportional to the number of atoms in it, it follows that the gravitational force between the objects must also be proportional to the product of their masses:
$$F = N_1 \cdot N_2 \cdot f_0 = \frac{M_1}{m_0} \cdot \frac{M_2}{m_0} \cdot f_0 = M_1 \cdot M_2 \cdot \frac{f_0}{m_0^2}$$
Note that, strictly speaking, this thought experiment doesn't exclude the possibility that objects made of different kinds of "atoms" might have different constants of proportionality between their mass and their gravitational influence depending on their composition.  (The fact that, according to experimental results, this does not actually happen in the real world basically amounts to the equivalence of inertial and gravitational mass.)  This thought experiment does, however, show that, for objects of the same composition, expecting the gravitational force between them to scale by anything other than the product of their masses would lead to seemingly absurd conclusions (i.e. the gravitational force between two lumps of atoms would vary depending on whether we consider each lump as a single object or as a collection of many objects).
A: The multiplication gives a force that fits experimental results, the addition does not.
A: 
we do M1×M2 and not M1+M2, why?

Certainly one reason, even without appealing to observation, is that it is reasonable to expect that if the gravitational "charge" (gravitational mass) is zero for either object, there should be no gravitational force between the objects.
If, say, $M_2 = 0$ and the force were proportional to the sum, we would have the absurd result that there is a gravitational force between object 1 and something that is gravitationally "nothing".
A: You've said in a previous question that you're a layman, and implied that you're suspicious of General Relativity, so this answer may not delight you. For anyone willing to accept GR this is the reason why the Newton formula for gravity contains the product of the masses.
Newton's formula is just a hypothesis that fits observations. Exactly how Newton came up with it only he will ever know, but he devised it at about the same time Kepler was making the first observations that planets moved in elliptical orbits round the Sun, and Newton's formula predicts exactly this behaviour. So all we can say is that it was a guess that worked.
To go further you have to accept that GR is a good model for gravity, and that the Schwarzschild solution is a correct solution for the gravitation outside a spherically symmetric body. Assuming you do accept this, twistor59's beautifully clear answer here describes how to calculate the coordinate acceleration relative to a stationary observer at the same point, and the result is:
$$ a = \frac{GM}{r^2}\frac{1}{\sqrt{1-\frac{2GM}{c^2r}}} $$
where $M$ is the mass of the planet/Sun/whatever, and from Newton's first law, $F = ma$, the corresponding force is:
$$ F = \frac{GMm}{r^2}\frac{1}{\sqrt{1-\frac{2GM}{c^2r}}} $$
where $m$ is the mass of our test object, and $F$ is the force on the test object. To get the Newtonian limit, we assume the mass of the planet/Sun/whatever is small enough that
$$ \frac{2GM}{c^2r} << 1 $$
and the equation above simplifies to:
$$ F = \frac{GMm}{r^2} $$
which is of course Newton's law of gravity.
Out of interest, at the surface of the Sun (the point of highest gravity in the Solar System) the difference between the force calculated using Newton's law and the full GR calculation is a factor of 1.000002, so Newton's law is an excellent approximation everywhere in the Solar System.
A: Let me answer this question in another intuitive way. If the gravitational law was $F=-\frac{\mathcal G(M_1 + M_2)}{R^2}$(with appropriate units for $\mathcal G$) then what would happen if we drop different object from a building?
$$a=\frac{\mathcal G}{R_{\oplus}^2}(1+\frac{M_\oplus}{M_\text{object}})$$
which is way much counter intuitive. If it was true it meant that a feather would accelerate towards earth much faster than a heavy lead ball; which even Galileo didn't expect to be true.
A: Consider Lego blocks of mass being attracted by an other object. The force on each block is $f$. What would happen if we take 3 blocks together?
As they are still 'separate objects' we can conclude that force is $3f$. In general for the $n$ objects it would be $nf$. But the mass of objects is also proportional to $n$ - hence force is proportional to mass.
For the addition formula to work:


*

*You would need to have a 'magic' step what is single object. While there is no technical reason why it could not be defined it's very counter-intuitive - does ocean count as an object - the molecules are not chemically binded - does 2 lego blocks count as one when combined etc.

*You would have a basic object for which the additive formula would work - say protons, atoms or quarks. But then on macroscale you will recover the multiplication formula (see paragraph above) - so for us it would look like either as the formula just works (if one object dominated) or it would be very complicated to figure out (if there was a mix).

A: One can "derive" this formula intuitively. 
Imagine every unit of mass being able to trap certain massless particles, call them "gravitons", that are coming randomly from all direction. As the unit of mass gets hit by a graviton it received a certain momentum in that direction and prevents the trapped graviton from hitting anything else.
With the above picture the mass $M_1$ would create a "shadow" from gravitons at distance $r$ proportional to $M_1$ and inversely proportional to the area of the sphere of radius $r$. Therefore at distance $r$ there are $const\cdot M_1/r^2$ fewer gravitons coming from the direction of $M_1$ than coming from the opposite direction.
Now suppose there is a mass $M_2$ at distance $r$ from $M_1$. Remember, that the chance of trapping a graviton is proportional to the mass, so the mass $M_2$ would trap $(const\cdot M_1/r^2)\cdot M_2$ fewer gravitons from the direction of $M_1$ than those directed toward $M_1$. Therefore the net force exhibited on $M_2$ in the direction of $M_1$ would be $const\cdot\frac{M_1M_2}{r^2}$.
