The perception of a pitch is due to the frequency of vibration of the hairs in the cochlea (the spiral-shaped organ in the inner ear), which is, in turn, driven by the vibration of the eardrum. Anything that drives the eardrum at a given frequency, say 440 Hz, will be perceived as the same pitch, regardless of medium.
What the medium does affect, however, is the speed of sound (v), which determines the relationship between frequency (f) and wavelength (L) according to the equation v = f * L. The physical mechanisms of many instruments are such that they create a tone of a fixed wavelength rather than a fixed frequency. For example, an organ pipe will create a standing wave with a wavelength determined by the length of the pipe. If the pipe is tuned to produce 440 Hz at room temperature, than changing the temperature of the air -- or its humidity, density, or even completely changing the medium -- will cause the speed of sound to change. As a result, the frequency it produces will be different, and it will be perceived as a different pitch. Organ tuners are always careful to tune organs at room temperature, and if the organ is played at a different temperature, it may sound out of tune.
Incidentally, this is also why breathing helium creates such a funny sounding voice. The shape of the mouth and the tension of the vocal cords fix the wavelengths that are produced, but the lighter medium allows the sound waves to travel faster, so they have a higher frequency. When the waves exit your mouth into the "regular" atmosphere, they retain their frequency, and it is the wavelength that changes to accommodate the slower speed of sound.