We have investigated the dielectric anomalies associated with spin ordering transitions in the tetragonal spinel Mn$_3$O$_4$, using thermodynamic, magnetic, and dielectric measurements. We find that two of the three magnetic ordering transitions in Mn$_3$O$_4$ lead to decreases in the temperature dependent dielectric constant at zero applied field. Applying a magnetic field to the polycrystalline sample leaves these two dielectric anomalies practically unchanged, but leads to an increase in the dielectric constant at the intermediate spin-ordering transition. We discuss possible origins for this magnetodielectric behavior in terms of spin-phonon coupling. Band structure calculations suggest that in its ferrimagnetic state, Mn$_3$O$_4$ corresponds to a semiconductor with no orbital degeneracy due to strong Jahn-Teller distortion.