Fear not! You are not alone in your confusion. While it is common these days to teach that forces are vectors and follow vector addition (as the other answers beautifully present it), historically, you have hit upon a quandary that lay at the center of a dispute throughout much of the 19th century, involving such characters as Newton, Lagrange, Heaviside, Poisson, Maxwell, Bernoulli, De Morgan, Young, Earnshaw, to name a few you might recognize.
For a full account of all of the back and forths that transpired and a full analysis of the weights of the arguments presented, please see A Tale of Two Vectors by Marc Lange (2009) [doi][pdf], which served as my introduction to the controversy, and reference for preparing what follows.
Just as you hint in your answer, that forces ought to add as vectors is entirely intuitive, and so it is not well known who first came up with the idea. Throughout time, everyone agrees on what the answer should be when you add two forces (as you can readily test in everyday life), but the dispute lay in exactly why it should take the form that it does. There are hints that it appeared in a lost work of Aristotle (384 - 322 B.C.E), and it definitely appeared in Heron's Mechanics (first century A.D.) [cite]
Newton and dynamics
But it was in Newton's Principia (1687) [wikisource] that we see the first proof, right at the top in Corollary I:
Corollary I: A body by two forces conjoined will describe the diagonal of a parallelogram, in the same time that it would describe the sides, by those forces apart.
If a body in a given time, by the force $M$ impressed apart in the place $A$ should with a uniform motion be carried from $A$ to $B$; and by the force $N$ impressed apart in the same place, should be carried from $A$ to $C$; complete the parallelogram $ABCD$, and by both forces acting together, it will in the same time be carried in the diagonal from $A$ to $D$. For since the force $N$ acts in the direction of the line $AC$, parallel to $BD$, this force (by the second law) will not at all alter the velocity generated by the other force $M$, by which the body is carried towards the line $BD$. The body therefore will arrive at the line $BD$ in the same time, whether the force $N$ be impressed or not; and therefore at the end of that time it will be found somewhere in the line $BD$. By the same argument, at the end of the same time it will be found somewhere in the line $CD$. Therefore it will be found in the point $D$, where both lines meet. But it will move in a right line from $A$ to $D$, by Law I
So, here Newton proves that force addition should take the form of vector addition (vectors won't be invented for a good 150 years), and gives as his proof a dynamical proof, one founded on the ideas of dynamics. He uses the motion that would be created by the forces on some hypothetical mass $m$, by his law of motion $\vec F = m \vec a$ to prove how forces should add given we know how the paths add.
This would give birth to the controversy, between the those in the dynamic camp, and those in the static camp.
I think Bernoulli† gave the most compelling damnation of the dynamical proof, in which he points out that even if were to live in a universe where Newton's law didn't hold, but instead some other law $\vec F = m \vec v$, say, forces would still add by the parallelogram law, so the ultimate reason that forces add in this way must be independent of dynamics itself.
†: Here Daniel Bernoulli, the one of the many famous Bernoullis responsible for Bernoulli's principle
Duchayla and statics
As an alternative to the dynamical explanation of Newton, the static proof usually given is ultimately traced back to Charles Dominique Marie Blanquet Duchayla (a name if I ever saw one) in 1804. In which his proof proceeds by induction, with the inductive step:
If forces $P$ and $Q$, acting together at a point, result in a force directed along the diagonal of the parallelogram representing the two forces, and likewise for forces $P$ and $R$ acting together at the same point, with $R$ acting in $Q$'s direction, then likewise for $P$ together with the resultant of $Q$ and $R$.
And proof of the inductive step:
Let $P$ be represented by segment $AB$. Grant that the resultant of $Q$ and $R$ is in their common direction and equal in magnitude to the sum of their magnitudes; let it be represented by segment $AE$, with $Q$ represented by $AC$, so that segment $CE$ is the proper length and direction to represent $R$ except that $R$ is actually applied at $A$ rather than at $C$. Nevertheless, when a force acts on a body, the result is the same whatever the point, rigidly connected to the body, at which it is applied, provided that the line through that point and the force's actual point of application lies along the force's direction.
So although $R$ is applied at $A$, its effect is the same if it is applied at $C$, since $AC$ is in the forces' direction. Continuing to treat the parallelograms in figure as a rigid body, we can move the three forces' points of application to other points along the forces' lines of action without changing their resultant. We cannot move $P$'s point of application directly to $C$, since $AC$ does not lie along $P$'s direction. But by hypothesis, the resultant of $P$ and $Q$ acts along diagonal $AD$, so the resultant can be applied at $D$. It can then be resolved into $P$ and $Q$, now acting at $D$. $Q$'s direction lies along $DG$, so $Q$ can be transferred to $G$. $P$'s direction lies along $CD$, so $P$ can be transferred to $C$, where it meets $R$. By hypothesis, their resultant acts along diagonal $CG$, so it can be transferred to $G$, where it meets $Q$. By the converse of the force transmissibility principle, $AG$ must lie along the line of action of the force resulting from $P$ composed with resultant of $Q$ and $R$...
Quotation and figure reproduced from Lange's paper
The proof goes on from here to establish that you can also demonstrate that it gets both the directions and magnitudes right, for a full reproduction, see Lange's paper.
This proof is a bit hard to read, and reviews were mixed, some thought it was the best thing since sliced bread, "very simple and beautiful", such as Mitchell, Young, Imray, Earnshaw and Pratt, other's, not so much:
forced and unnatural... a considerable waste of time
Besant 1883, Lock 1888
the proof of our youth... now voted cumbrous and antiquated, and only retained as a searching test of logical power
A.G.G. 1890
brainwasting... elaborate and painstaking, though benumbing
Heaviside 1893
certainly convincing...but...essentially artificial...cunning rather than honest argument
Goodwin
Poisson and symmetry
But not all is lost. Poisson offered an alternative proof of the static case in 1811, which is based on symmetry arguments, dimensional considerations and a uniqueness constraint. I quite like this version. You start by assuming you have two forces of equal magnitude $P$ but different directions, separated by an angle $2\theta$ (The red forces in the diagram). Invoking rotational invariance and symmetry, the resultant $R$ (black) must bisect the two in direction, and its magnitude must be a dimensionally consistent formula of the magnitude of $P$ and the angle $\theta$ alone, or of the form:
$$ R = P g(\theta) $$
with some unknown function $g(\theta)$. To figure out the function, Poisson then considers two new problems:
At the top and bottom, we've set up two new copies of the same task, now adding pairs of forces $Q$ (blue) to create the $P$s, and can see that
$$ P = Q g(\phi) \implies R = Q g(\theta) g(\phi) $$
Meanwhile the two inner $Q$ forces (slightly darker blue) and two outer $Q$ (slightly lighter blue) forces set up the same scenario, all four of them adding to the resultant $R$, and each pair a part, and since we assume that forces in the same direction just add in magnitude, we have also
$$ R = Q g(\theta + \phi) + Q g(\theta - \phi) $$
together:
$$ g(\theta) g(\phi) = g(\theta+\phi) + g(\theta-\phi) $$
the only solution to this functional equation are solutions of the form:
$$ g(\theta) = 2 \cos (\alpha \theta) $$
with an unknown $\alpha$, but we can fix $\alpha = 1$ by requiring that equal forces in opposite directions cancel. So finally we recover the force addition formula for equal magnitude forces:
$$ R = 2 P \cos \theta $$
cast in polar form. From here it is easy to generalize to the full vector addition results by decomposing forces into various pieces.
I'm quite fond of this proof as it relies only on symmetry and dimensional considerations, and is completely free from any discussion of dynamics. But, some people equate this to a deficit:
Many have been puzzled by finding that the thing which, by its very definition tends to produce motion, is reasoned on... under a compact that any introduction of the idea of motion would be out of place. The statical proofs... seem to be all geometry and no physics
Augustus De Morgan (1859)
But others find it quite elegant:
The proof which Poisson gives of the "parallelogram of forces" is applicable to the composition of any quantities such that turning them end for end is equivalent to a reversal of their sign
Maxwell in 1873
Onto the philosophical
Nowadays, people continue to argue over the force addition law's origins, but mostly in philosophy journals. But In the second half of Lange's paper, he summarizes these various philosophy arguments and comes to the rough conclusion that in the end, whether you want to believe a dynamical or static origin is sort of question of interpretation, similar to whether you want to believe Newtonian Mechanics of Lagrangian mechanics. It's up to you to decide for yourself. The historic lineup of heavyweights is roughly:
In the dynamic camp:
- Newton
- Lagrange
- Heaviside
- De Morgan
In the static camp:
- Poisson
- Maxwell
- Bernoulli
- Young
- Earnshaw
Where will you stand?
