New low-resolution UV spectra of a sample of reddened OB stars in M31 were obtained with HST/STIS to study the wavelength dependence of interstellar extinction and the nature of the underlying dust grain populations. Extinction curves were constructed for four reddened sightlines in M31 paired with closely matching stellar atmosphere models. The new curves have a much higher S/N than previous studies. Direct measurements of N(H I) were made using the Ly$alpha$ absorption lines enabling gas-to-dust ratios to be calculated. The sightlines have a range in galactocentric distance of 5 to 14 kpc and represent dust from regions of different metallicities and gas-to-dust ratios. The metallicities sampled range from Solar to 1.5 Solar. The measured curves show similarity to those seen in the Milky Way and the Large Magellanic Cloud. The Maximum Entropy Method was used to investigate the dust composition and size distribution for the sightlines observed in this program finding that the extinction curves can be produced with the available carbon and silicon abundances if the metallicity is super-Solar.