How could they tell things weigh a sixth of their "Earth weight" on the moon? I frequently keep hearing stuff about "gravity on the moon is only a sixth of that as Earth's" and "of course you'll weigh more on Jupiter". I do know the relative sizes of those bodies allow for gravitational acceleration that's different from the $9.8 \mathrm{\; m\cdot s}^{-2}$ we're accustomed to here, and I'm pretty sure nobody's ever bothered to bring a scale to Mars or something.
How can one reckon how much you'll weigh on the moon if you don't know the "one-sixth" bit? How about on other planet(oid)s and satellites?
 A: For "the" Moon:
First, you need to know how big the Earth is. This is easily doable, using Eratosthenes' method - comparing the length of the shadow of a stick in Alexandria and Syene.
Then you can determine how massive the Earth is. Given its size, and the gravitational acceleration at the surface, you determine its mass.
Then, how big the Moon is. Well, during a Moon eclipse, assuming the Sun is very very far away, the diameter of the Earth's shadow is equal to the diameter of the Earth. So just look at the size and shape of the Earth's shadow on the Moon (a fraction of a circle) during an eclipse. Knowing the size of the Earth, it is easy to then determine the size of the Moon, by comparing the circle made by the Moon's circumference and the circle fragment made by Earth's shadow on it.
How far the Moon is? Once you know its size, just measure the angular diameter, do some basic trigonometry, and you get the distance.
Or you could do it the other way round, observing the Moon from two different places on Earth, knowing the distance between the places, and the angles the Moon makes with the horizon in both places. Then you could determine the Moon-Earth distance via trigonometry.
Alternatively, nowadays the Earth-Moon distance is measured very precisely by bouncing a laser off a reflector installed on the Moon, and tracking the reflection with a telescope and measuring the total propagation time.
How quickly do the Moon and Earth rotate around their common mass center? That's easy, just measure it by simple observation, just keep observing the sky and you'll figure it takes about 4 weeks.
At this point, you know how big are the Earth and the Moon, what is the distance between them, how heavy is the Earth, and how quickly they rotate around each other. The only unknown in the equation is Moon's mass, which is deduced via newtonian mechanics.
Having Moon's mass and its diameter, it is easy to determine the acceleration on its surface, again via Newton.
For other moons and planets:
It depends. The orbits of the planets were determined via many thousands of observations. Once you assume the Sun is in the middle and everything else runs around it, then all those many observations could only fit elliptical orbits of certain size and shape (this is not easy to explain intuitively, there's a lot of math). This was done before telescopes by Tycho Brahe and Kepler.
So, you know Venus' orbit, and Earth's. You do the math, and figure that at this moment, the distance between them is X. You look thought the telescope, and measure Venus' angular diameter to be 50 arcsec. Now do some basic trig, and you'll determine its diameter. Easy.
How heavy is Venus? Having no satellites, you can't tell. You need to wait for a comet to be deflected, or you need to send a space probe to orbit around it.
Or you could measure the tiny variations in Earth's orbit caused by Venus, and estimate Venus' mass that way. But this is not very precise.
Mars is easier, it has satellites already, so you can determine its mass. Same for Jupiter, Saturn, etc.
A: This value of how much you or an object will weigh on another body is based on the basic equation for gravitational acceleration.  Effectively, the acceleration from gravity is a function of the mass of an object and how far from its center you are:  $G\cdot M/r^2$.
You can run the math if you want to, plugging in $G$ ($6.67\cdot10^{-11}$ m3/(kg*s2)), the mass of Earth, and the radius, and you'll arrive at the value you quoted.  Do it for the moon, and you'll get about 1/6 Earth's.
You could also do this as a ratio:  Take the ratio of the mass of the object (moon's mass is 1/81 Earth's) and the radius of the object (moon's radius is about 1/3.7 Earth's), and do the math as a ratio:  (1/81)/(1/3.7)2 = 0.171, or about 1/5.8 Earth's gravity.  You can do the same for other objects.
And you can actually measure this on the moon based on how quickly objects fall.  People who claim that the film was slowed down by 2x to give the illusion of being on the moon have never done this calculation because they would get the wrong answer for Earth if they sped the film up by 2x.
A: "Orbits", and the observation of their properties, are the key notions here. 
For example, a lunar module in a stable low Moon orbit is observed to fly at $1.3{\rm km s^{-1}}$ along the Moon's surface. Given the Moon's radius, these data uniquely define the gravitational acceleration on the Moon's surface. So you'll know simply from your Doppler radar measurement of your aircraft's speed how much you're going to weigh before you set foot outside your LEM!
Likewise, astronomical observations of, e.g. the Galilean satellites of Jupiter allowed astronomers to know in advance the gravitational acceleration near the surfaces of planets long before even the Cavendish experiment gave us a value for the universal gravitation constant $G$.
