At the [Bristol Hackspace](http://bristol.hackspace.org.uk) this evening, I powered up a Hall sensor.
The Allegro A1321 takes a 5v supply and outputs 2.5v - plus or minus 5mV per gauss of magnetic field in the sensor.
It turned out that small magnets don't produce many gauss, so I added a 741 op-amp with a gain of about 100 to get more useful output voltage deflection!
Here's the experimental setup:

WIth no nearby magnets, we read about 3v:

But with a very nearby magnet, we get a large deflection, which drops as we get the magnet many cm away, but is still significant:

Clearly we still get significant readings a good distance away, and the nonlinearity isn't too bad; it doesn't max out with the magnet very close but still varies many cm away.
For my next trick I'll make a few of this circuit on some veroboard and hook the outputs up to an AVR with several ADCs that I have lying around, and try comparing the results to measure position (and maybe orientation?) of a magnetic probe...