The mass of the object always stays the same. The balance can only measure the downward force exerted on it by the bob. The force measured by the balance is simply the weight of the masses on one side needed to balance the downward force of the bob on the other side.
In air, the only appreciable force will be the downward force from gravity, aka the weight of the bob. In water, there is also a significant upward force due to the buoyant force exerted on the bob by the water. So in the water, the balance is measuring the difference between the weight of the bob and the buoyant force. The relevant physics and formulas can all be found on Wikipedia easily. If you define the (true) specific gravity $S$ as the ratio of the density of your bob $\rho_B$ to the density of water, i.e. $S = \frac{\rho_B}{\rho_{H_20}}$, you should be able to show that
$$ \frac{f_{water}}{f_{air}} = 1 - \frac{1}{S},$$
where $f_{air}$ and $f_{water}$ are the forces measured by your balance in air and in water respectively.
Regarding the use of grams or Newtons, they are often used interchangeably to talk about the weight of an object, although this is technically rather sloppy because they are not the same thing in general. The two units measure fundamentally different things, one is a mass and one is a force. However, since all objects on the Earth are subject to the same acceleration $g$ due to gravity, there is a natural way to change between one and the other, by the formula $f = mg$. Whenever people use grams to measure forces, or Newtons to measure mass, it is this correspondence that they are implicitly referring to.
You ask, "How do we describe mass to the aliens, who don't know about our (g)?" This is an example of a class of questions referred to by Martin Gardner as "Ozma problems." The classic Ozma problem is how we describe to aliens the distinction between right and left; the answer is that we do it by describing the weak nuclear force.
Your statement of your Ozma problem seems a little ambiguous to me. Essentially you're asking how we describe to the aliens a unit of gravitational mass. (You don't say so explicitly, but it seems clear from context that you don't mean inertial mass.) Futhermore, there is a distinction bewteen active gravitational mass (the ability to create spacetime curvature) and passive gravitational mass (what we measure with a balance). Not only that, but your question could be interpreted as asking whether we can compare with the aliens and see whether the value of the gravitational constant $G$ is the same in their region of spacetime as it is in ours.
We can easily establish 1 g as a unit of inertial mass. For example, we can say that it's the inertia of a certain number of carbon-12 atoms.
The equivalence principle holds for us, so presumably it holds in experiments done by the aliens as well. This establishes that our 1 g unit of inertial mass can also be used as a unit for the passive gravitational mass of test particles.
You didn't ask about active gravitational mass, but the equivalence of active and passive gravitational mass is required by conservation of momentum, and has also been verified empirically in Kreuzer 1968. Cf. Will 1976 and Bartlett 1986.
The other issue is whether $G$ is the same for the aliens as for us. Duff 2002 has an explanation of the fact that it is impossible to test whether unitful constants vary between one region of spacetime and another. However, there are various unitless constants that involve $G$, such as the ratio of the mass of the electron to the Planck mass.
A more fundamental difficulty in the fundamental definition of mass is that general relativity doesn't seem to offer any way of defining a conserved, global, scalar measure of mass-energy. See, e.g., MTW, p. 457
Bartlett, Phys. Rev. Lett. 57 (1986) 21.
Duff, 2002, "Comment on time-variation of fundamental constants," http://arxiv.org/abs/hep-th/0208093
Kreuzer, Phys. Rev. 169 (1968) 1007
MTW: Misner, Thorne, and Wheeler, Gravitation, 1973.
Will, “Active mass in relativistic gravity: Theoretical interpretation of
the Kreuzer experiment,” Ap. J. 204 (1976) 234, available online at adsabs.
harvard.edu.
Best Answer
There's a thing called a "slug". " It is a mass that accelerates by 1 ft/s2 when a force of one pound-force (lbF) is exerted on it." (wikipedia).
Sometimes you'll see reference to a "pound-mass" to indicate a mass which weighs one pound at sea level (on Earth, thank you! :-) ).
The problem is that pounds and kilograms have been used colloquially since forever to describe the weight of objects. Scientific usage differs from informal usage such as "shipping weight".