A hall sensor is a semiconductor that senses a magnetic field and returns a signal according to the intensity of it (more info on the hall effect can be found on wikipedia
http://en.wikipedia.org/wiki/Hall_effect ).
There are several types of hall sensors. The most common, normally found in small brushless motors, is a hall switch: if the magnetic flux is above a set limit, the sensor will act like a closed switch. We don't normally need those.
Another sensor is a quadrature encoder, that will return either two signals based on the angle of the magnetic field or a single digital signal with a number representing the angle measured. they are expensive and require more processing logic than the average joystick can provide, and we don't use these either.
What we look for are ratiometric hall sensors, or linear hall sensors. These will have three pins, one connected to ground line (generally 0 volts), one connected to the +V line (in usb and gameport joysticks this is usually +5 volts) and a third pin where we pick up the signal. This signal will swing between slightly more than ground and slightly less than +V, the value depending on the intensity of the magnetic field going through the sensing area and the sensor specs. Generally no magnetic field will return a voltage exactly halfway between ground and +V. Magnetic fields have both an intensity and a direction, and the sensing area will read a magnetic field parallel to it as no magnetic field. This means that if we can create a magnetic field where the flux lines are fairly parallel, we can use the hall sensor to translate the angle between the magnetic field and the sensor into a voltage. this makes the hall sensor almost a drop in replacement for a potentiometer, at least on newer joysticks, with the caveat that you must take care of the ways the pins are connected to the power lines, or you will burn the sensor out.
Now, why did I say "almost"? Well, hall sensors are more accurate than potentiometers and the signal quality won't degrade with wear, but they don't respond exactly like potentiometers. their sensing "angle" is different, the response is not really linear (but we can ignore it if we keep to smallish angles), they can't swing through the whole range from ground to +V unless you add some complex conditioning circuitry, and they can only provide you a voltage and not a resistance. the last bit means that you can't use them in old gameport devices, because the gameport reads resistance rather than voltage (which is also why it loses calibration so easily and so often) but that is hardly a problem nowadays.