Stan has essentially answered this in his comment, which I will attempt to spell out a little more laboriously.
The significant majority of our Sun's energy output comes from the proton-proton chain. This was advocated by Eddington back in the 1920's, but at that time your basic concern was a very real and major problem. Objects with like electrical charges repel each other. In particular, protons will repel other protons since all protons have a positive charge. What they knew of the sun then indicated that the core was far too cold for protons to overcome this repulsion—at least not even remotely close to the rate that was obviously necessary to produce a brightly shining sun.
With the development of quantum mechanics it was determined that a process known as quantum tunneling would give two protons a non-zero probability of "overcoming" this repulsion. But not in the sense of they just suddenly gain enough energy (hence why "overcoming" is in quotations). Instead, in the sense that the "fused together" state has the same energy as the "just about to repel each other before fusion can occur" state, and they just randomly switched from the latter to the former, despite every intermediate stage between the two of them requiring more energy than is available. That this is possible is one of the many non-intuitive features of quantum mechanics, and I think it would be beyond the scope of this question (and site) to try to get much more precise.
Still, even this failed to explain why our sun was very obviously fusing atoms to the extent that it was. If you fuse two protons together, you are left with an incredibly unstable state: the diproton. As soon as one of these forms it pretty much immediately breaks up into two distinct protons.
In the late 30's Hans Bethe (a man who eventually won the Nobel prize and was a part of the Los Alamos team that developed the atom bomb) proposed that yet another random quantum mechanical event would save the day: beta decay, a feature of the recently discovered fundamental force known as the weak force. In this situation one of the protons in the diproton undergoes a beta decay into a neutron before the diproton separates, at which point you have a stable deuterium nucleus: one proton, and one neutron.
That so many unlikely events have to occur for two protons to produce one deuterium is the reason why the sun's lifetime is approximately 10 billion years. That the sun shines as bright as it does is, as you suggest, a sheer numbers game: there are truly prodigious numbers of protons in the sun's core, so even though the proton-proton chain is really unlikely, we have so very many chances at it that there is a great many successful fusion events.
Basically every other stellar fusion reaction proceeds much more rapidly than those that produce deuterium. You may be familiar with the hydrogen bomb, which fuses its fuel very rapidly. One of the key differences (and there are many) between the hydrogen bomb and a star like our sun is that the bomb is fusing together deuterium (and tritium) into helium, and is not using the proton-proton chain. Stars have to produce large supplies of deuterium directly, and this is a lengthy process that consumes roughly 90% of a star's life—even for very massive stars, whose lifespans are orders of magnitude shorter than our Sun's.
(Note that very massive stars are rather more complicated beasts, in fact, but this is again beyond the scope of this question)
