I don't know the historical answer. We have the benefit of much more developed mathematical tools. I think that he used mostly geometry and never expressed it in the modern format at all. Perhaps someone with more knowledge of Principia can comment on the history.
All Newton did was state that the force of gravity between two masses is directly proportional to the product of the two masses and inversely proportional to the square of the distance between those masses.
F = k m1m2 / r2, leaving for others to find the value of k which makes both sides equal.
Henry Cavendish was the first scientist to perform experiments which accurately determined the value of k to use to find the force of gravity between two masses, knowing the value of these masses and the distance between them. He performed these experiments in 1797-98:
At the time when Cavendish was working, he was trying to measure the mass or density of the earth, which is the result he actually published. Years later, his experiments were reviewed and the results were converted into an equivalent value of the constant G, which is currently used in modern statements of Newton's Law of Universal Gravitation.
Incidentally, the type of apparatus which Cavendish designed and built, a torsion balance, is still used in experiments to measure the value of G. However, because of the inherent limits of such an apparatus, the value of G is one of the fundamental physical constants which is least accurately known.
Just as previous posters have said, although Newton was an expert at algebra – after all he pioneered using binomial series for negative and fractional indices – he didn't use algebraic formulae for all the purposes that we would. So, having conceived of an inverse square law (or possibly having heard it suggested by Hooke or some other contemporary) he could compare the Earth's field (as we would say) at different distances from the Earth without ever using an equation with a constant in it.
I agree that Newton did not express or contemplate about a number for G. His careful experimental verifications involved various data about Jupiter's moons, Saturn's moons, the Earth-Moon system and the planetary orbits around the sun. He did not need the exact values of the masses of the bodies (although he could estimate ratios of masses), nor did he need to know anything about G to get the theory proved.
What he did figure out is ...
1. Verification of the inverse square law and the proportionality to the product of the masses.
2. Proof that spherical masses acted as a point mass at the center
3. Identification that the law of gravitation was universal in that it applied to the Jovian system, the Saturnian system, the Earth-Moon system and the solar system.
4. Indication that these systems approximately behave as independent systems, but still there is interaction between them (e.g. the Sun effects the Earth-Moon's orbit or the interaction of Saturn and Jupiter).
5. Discovery of the equivalence of inertial mass and gravitational mass.
6. Estimation the ratio of masses relative to the sun for several planets and got Jupitor correct to less than 2% error (wow!)
7. Employment of linear superposition in his theory
8. Demonstration that the true center of the solar system is not the "earth" or "sun" but as a center of gravity near the sun.
Of course , he did a heck of a lot more than just these things. But, these are some of the things that helped identify the concept of G, even if he never dealt with its numerical value.