The magnetic field changes a tiny bit each time a tooth on the gear goes by.
This causes a tiny change in the voltage across the hall sensor.
The tiny change in voltage is amplified, then fed through a comparator that outputs a nice square edged signal each time it detects a tooth.
You really ought to take a look at how hall effect sensors work.
How it works is fascinating, and the extreme small size of the effect (and what it takes to make a simple, reliable, easy to use sensor) ought to make you appreciate the ingenuity of those unsung engineers who make it "just work."
You have basically a physics lab full of precision instruments packed into one little chip.
The basic effect is caused by the magnet deflecting the electrons moving in one direction through a conductor. The magetic field makes them take a slightly curved path which results in more electrons flowing on side side. The result is a voltage across the conductor perpendicular to the flow of current. (Paraphrased from Wikipedia.)
Pretty much any (relatively) sudden change in the magnetic field will cause a pulse in the output.
If you wire up such a sensor so that it can work, you can observe the output with an oscilloscope.
Waving a screwdriver tip across the face of the sensor will cause pulses to appear.
How far the screwdriver (or other magnetic object) can be from the sensor depends on how strong the magnet is, and how sensitive the hall sensor is - which is related to how thin the sensor's internal conductor is. Thinner is more sensitive.
The original experiments used gold leaf as the conductor in the sensor, and fairly high currents to get a high enough voltage to be detectable.