Is it possible for ordinary table salt (sodium chloride) to form on a lifeless planet / moon / comet / other body? Is liquid water required? Would it be common or nearly-impossibly rare? Part of a novel I'm reading takes place in a salt mine on a moon with liquid water (similar to current theories about Europa.)
Chlorine is a relatively rare element, so the concentrations of it is not going to be high anywhere. It is also very reactive, so all of it is likely to only occur as a part of different chemical compounds. Chlorine is especially likely to react with sodium as it one of the most common elements, and also has a very low electronegativity.
That makes sodium chloride a very polar compound, and since water is also a polar molecule, salt dissolves easily in water. Water flowing over the crust of a planet for thousands of years slowly extract the salt from the ground, and can leave it as concentrated deposits when it evaporates. Thus liquid water is required for any significant concentrations of salt.
This creates a border between the worlds that have liquid water (or had, Mars has salt deposits), and those that do not. One notable exception is the chlorine detected in the erupted material from Io, making table salt at its surface a possibility.