You have to realize that when we are speaking of photons, we are speaking of elementary particles and their interactions are dominated by quantum mechanics, not classical mechanics, and in addition special relativity is necessary to calculate anything about them.
In general, we know about elementary particles because we observe their traces in detectors for almost a hundred years. We never see an electron, or a proton in the way we see a particle of dust.
This is the most visual detector, a bubble chamber photo of electromagnetic events.
Here we see some electromagnetic events such as pair creation or materialization of high energy photon into an electron-positron pair (green tracks), the Compton effect (red tracks), the emission of electromagnetic radiation by accelerating charges (violet tracks) (bremsstrahlung) and the knock-on electrons or delta ray (blue tracks)
Now lets see about your questions:
1) How did we arrive at "electrons exchange virtual photons and that's the cause of the electromagnetic force between them" from merely observing electrons absorbing or emitting photons?
That is not the way we arrived at this conclusion. A very large number of controlled scatterings, which is what this picture shows, of electrons on matter have been studied over the years and the theoretical framework of calculating the probability of the scatter and the angular distributions has been very well developed for years. This involves mathematics which cannot be handwaved. To start with, the crossection of an electron scattering on an electron can be written in a series of convoluted integrals which can be pictorially represented by Feynman diagrams. In those Feynman diagrams, the propagators of the interaction between the incoming and outgoing particles can be thought as virtual photons because they carry the quantum numbers of the photon but are off mass shell. So it is a convenient mathematical identification which defines virtual photons.
Anything between the incoming vertices and the outgoing vertices is virtual, and their reality depends on the correct representation of the quantum numbers for the exchanged particle, in this case photon quantum numbers.
2) If electrons throw photons at each other doesn't that mean that they should only scatter (repel)? If that is so why do magnets attract?
Virtual photons are not like balls, they are off mass shell, they are useful a mathematical construct .There is an interesting analog though where two boats throwing balls at each other represent the repulsive forces, and boomerangs the attractive.
Do these two phenomena happen here on earth naturally (no LHC or other particle accelerators), in the upper atmosphere, or only in the deep dark space?
There exist cosmic rays of all energies, the cosmic accelerator, and elementary particles were first seen in emulsions exposed to cosmic rays in high altitudes, for example the pion was thus discovered. So any process seen in accelerators can be found if looking hard enough in cosmic rays. Accelerators allow detail and exact measurements of crossections and branching ratios etc. because of the high statistics possible.