Newton's law of gravitation operative near the earth is the same law causes the earth and the other planets to go around the sun and other heavenly phenomena. Was it a giant leap of faith by Newton or did he religiously studied astronomical data to come to this conclusion?
According to his own recollections, Newton arrived to the idea of universal gravitation when he compared the acceleration of the moon in its orbit with the acceleration of falling objects on the Earth surface. This was his first calculation. This was a rough, approximate estimate with many simplifying assumptions.
Many years later, Newton was able to show that the his attraction law is equivalent to the Kepler Law. This was a major step which made the universality of the law of gravitation much more plausible. After that he started to investigate other phenomena: the three bodies problem (that is deviations of the Moon from the Kepler laws), tides, the shape of the Earth, etc. And was convinced that the gravitation law can indeed explain these phenomena. He wrote his famous book, where he gave explanations of many celestial and other phenomena from the gravitation law.
His results were far from complete. For example, he could not explain all known at that time irregularities of the Moon motion. His prediction of the shape of the Earth was confirmed after many measurements (mostly French). His theory of tides was eventually developed to the extent which made tide prediction possible. A reasonably complete theory of Moon motion was developed (with enormous efforts of best mathematicians) by the middle of 18 century.
These investigations were curried on by his successors, gradually convincing more and more in the exactness and universality of the law. Some major steps were calculations of the orbits of small planets and the discovery of Neptun in the first half of 19 century.
The meaning of saying that gravitation is 'universal', as in the question posed in at least the title, is sometimes misunderstood. It refers primarily to the appreciation that all massive bodies attract each other: i.e. that heavy bodies gravitate at the same time towards all other massive bodies, and not only towards one local source of attraction.
There isn't one single historical document that explains how Newton arrived at this conception. But the time-period within which he arrived at the idea can be narrowed down, probably, to some time from late 1684 to early 1685, by two of the documents he wrote in that period.
The first of these relevant documents, from late 1684, is 'De motu corporum', an early precursor of what became the Principia: it contains no mention of anything that points to the universality of gravitation, so it may provide what can be called a terminus a quo. Its investigations focus entirely on the relation between the trajectory of a body in motion and a single source of centripetal force. For this idealised and simplified system, 'De motu corporum' demonstrates among other things the 'equal-area' character of the motion, and the relation between elliptical trajectories and an inverse-square law of centripetal force. But by its limitation to considering only one center of attraction, it lacks any sign that Newton at the time of writing it appreciated the universality of gravitation.
Probably the first document that does show a sign that Newton considered gravitation to be universal is a manuscript passage from early 1685 often known as the 'Copernican scholium' because it directly asserts among other things that the Copernican system is 'proved a priori' from gravitational considerations. The apparent purpose of this text was to memorialise just how immensely complex are the motions in the solar-system. The text appeals expressly to the laws of motion, and then also implicitly to ideas of the relative masses of the planets, mentioning in passing "the [attractive] action of all these [planets] on each other". (Newton's way to measure the relative masses of Sun, earth, Jupiter and Saturn did not appear in print until Book III of the Principia, but the text of the 'Copernican scholium' appears to presuppose and to indicate that when Newton wrote it he already had some of his ideas of solar and planetary masses and mutual actions of the planets, as well as appealing to his demonstrations of motion under centripetal accelerative force).
The message of the scholium (translated from Latin to English by J Herivel (1965) in 'The Background to Newton's Principia') is, in part,
"... the planets neither move exactly in ellipses nor revolve twice in the same orbit. So that there are as many orbits to a planet as it has revolutions, as in the motion of the Moon, and the orbit of any one planet depends on the combined motion of all the planets, not to mention the actions of all these on each other. But to consider simultaneously all these causes of motion and to define these motions by exact laws allowing of convenient calculation exceeds, unless I am mistaken, the force of the entire human intellect."
Thus the passage implies or presupposes a generalisation of the attractive actions of the planets, all exerting actions on each other.
It also seems that in early 1685 Newton thought it possible that such motions -- including the actions of all the planets on each other -- were so complex that they might never be solved mathematically. He did later develop initial steps towards solving such many-body motions (e.g. in Proposition 66 of Book I of the Principia) but the subject continued to provide many thorny problems for celestial mechanicians for centuries after Newton.
So far this answer concerns when rather than how Newton reached his idea of the universality of gravitation. For the 'how', there is much uncertainty. But if the logic and layout of Book III of the Principia are any indications, then it seems that Newton considered that the behavior of the satellites of Jupiter had great demonstrative significance for universal gravitation. The satellites clearly make their revolutions around Jupiter, with something as close to equal-area motion as observations of Newton's time could establish. Newton may have inferred initially that not only the Sun but also at least Jupiter must be sources of attraction -- and if both of those, then probably also the others, by his 'rules of reasoning in philosophy' (a heading that made its appearance only in later editions of the Principia, even though core principles were present in the first edition).
Newton's 'moon-test' appears not to concern this question about the universality of gravitation. The test had the purpose and effect of showing that the force that makes the moon deviate from a straight-line trajectory into its curved orbit around the earth has the same magnitude, when allowance is made for the inverse-square effect of distance, as the force that makes terrestrial heavy bodies tend to fall to earth. Only an attraction by the earth was considered: the moon-test was not designed to consider whether the moon (or terrestrial bodies) is also attracted by anything other than the earth. Newton's quantitative arguments used and acknowledged Huygens's meaure of the accelerative force of terrestrial gravity from pendulum experiments. The result supports that these forces are of the same kind as what causes the heaviness of ordinary bodies near the earth's surface. That was what Newton believed to justify describing the forces that accelerate the moon and by inference the planets as 'gravitational'.
The contributions of Hooke also do not seem to go to the universality of gravitation: he was a fine observer but had too little mathematics to develop the theoretical potential of his observations. His telescopic observations included noticing the character of the lunar craters, from which he made the astute inference that they arose by impacts, suggesting that heavy bodies would fall to the moon's surface as they fall to the earth's surface. But Hooke also wrote that the effects of the planets were exerted within their 'sphere of influence' -- a remark that appears to stop short of arriving at any idea of universal gravitation.
Newton considered himself to be not only rediscovering the mathematical principles of the ancient philosophers in his Principia, but also rediscovering the ancient geometrical methods. In an intended preface for the second edition written in 1710, Newton attributed knowledge of universal gravitation to the ancient Chaldaean and claimed that Pythagoras imported it to the Greeks and Romans. [p.23].