There are two essential facts that make a hole a hole:
Fact (1) The valence band is almost full of electrons (unlike the conduction band which is almost empty);
Fact (2) The dispersion relation near the valence band maximum curves in the opposite direction to a normal electron or a conduction-band electron.
Fact (2) is often omitted in simplistic explanations, but it's crucial, so I'll elaborate.
STEP 1: Dispersion relation determines how electrons respond to forces (via the concept of effective mass)
EXPLANATION: A dispersion relation is the relationship between wavevector (k-vector) and energy in a band, part of the band structure. Remember, in quantum mechanics, the electrons are waves, and energy is the wave frequency. A localized electron is a wavepacket, and the motion of an electron is given by the formula for the group velocity of a wave. An electric field affects an electron by gradually shifting all the wavevectors in the wavepacket, and the electron moves because its wave group velocity changes. Again, the way an electron responds to forces is entirely determined by its dispersion relation. A free electron has the dispersion relation $E=\frac{\hbar^2k^2}{2m}$, where m is the (real) electron mass. In the conduction band, the dispersion relation is $E=\frac{\hbar^2k^2}{2m^*}$ ($m^*$ is the "effective mass"), so the electron responds to forces as if it had the mass $m^*$.
STEP 2: Electrons near the top of the valence band behave like they have negative mass.
EXPLANATION: The dispersion relation near the top of the valence band is $E=\frac{\hbar^2k^2}{2m^*}$ with negative effective mass. So electrons near the top of the valence band behave like they have negative mass. When a force pulls the electrons to the right, these electrons actually move left!! I want to emphasize again that this is solely due to Fact (2) above, not Fact (1). If you could somehow empty out the valence band and just put one electron near the valence band maximum (an unstable situation of course), this electron would really move the "wrong way" in response to forces.
STEP 3: What is a hole, and why does it carry positive charge?
EXPLANATION: Here we're finally invoking Fact (1). A hole is a state without an electron in an otherwise-almost-full valence band. Since a full valence band doesn't do anything (can't carry current), we can calculate currents by starting with a full valence band and subtracting the motion of the electrons that would be in the hole state if it wasn't a hole. Subtracting the current from a negative charge moving is the same as adding the current from a positive charge moving on the same path.
STEP 4: A hole near the top of the valence band move the same way as an electron near the top of the valence band would move.
EXPLANATION: This is blindingly obvious from the definition of a hole. But many people deny it anyway, with the "parking lot example". In a parking lot, it is true, when a car moves right, an empty space moves left. But electrons are not in a parking lot. A better analogy is a bubble underwater in a river: The bubble moves the same direction as the water, not opposite.
STEP 5: Put it all together. From Steps 2 and 4, a hole responds to electromagnetic forces in the exact opposite direction that a normal electron would. But wait, that's the same response as it would have if it were a normal particle with positive charge. Also, from Step 3, a hole in fact carries a positive charge. So to sum up, holes (A) carry a positive charge, and (B) respond to electric and magnetic fields as if they have a positive charge. That explains why we can completely treat them as real mobile positive charges in their response to both electric and magnetic fields. So it's no surprise that the Hall effect can show the signs of mobile positive charges.
Best Answer
The Hall voltage is given by the equation
$$V_H = \frac{I~B}{n~e~d}$$
Where $I$ = current, $B$=applied magnetic field, $d$ = width of conductor, $n$ = density of mobile carriers, and $e$ is the charge of an electron.
The sign of the voltage depends on the predominant charge carrier, and it is possible to imagine a material where the positive and negative carriers cancel - this would be a material that doesn't exhibit a Hall effect.
Now an undoped (intrinsic) semiconductor has equal numbers of electrons and holes - because each electron that is thermally excited from its valence band leaves behind one hole. However, their mobility is typically not the same - so an intrinsic semiconductor will have higher mobility electrons, and the Hall effect will have the same polarity as N-type semiconductor. If you added a tiny amount of P-type dopant, you could increase the density of the holes to offset their lower mobility, and neutralize the Hall effect.
In fact, the drift velocity of the charge carriers is given by $v_D=\frac{I}{neA}$ (where $A$ is the cross sectional area). When the charge carrier density is very high, the velocity is very low (e.g. in good metallic conductors); when the carrier density is lower (semiconductors), the velocity is much higher. It is actually possible to move a conductor in a magnetic field at sufficient speed to make the Hall voltage disappear, and this can be used to measure the drift velocity.