The oxygen abundance gradients among nebular emission line regions in spiral galaxies have been used as important constraints for models of chemical evolution. We present the largest ever full-wavelength optical spectroscopic sample of emission line nebulae in a spiral galaxy (M31). We have collected spectra of 253 HII regions and 407 planetary nebulae with the Hectospec multi-fiber spectrograph of the MMT. We measure the line-of-sight extinction for 199 HII regions and 333 PNe; we derive oxygen abundance directly, based on the electron temperature, for 51 PNe; and we use strong line methods to estimate oxygen abundance for 192 HII regions and nitrogen abundance for 52 HII regions. The relatively shallow oxygen abundance gradient of the more extended HII regions in our sample is generally in agreement with the result of Zaritsky et al. (1994), based on only 19 M31 HII regions, but varies with the strong-line diagnostic employed. Our large sample size demonstrates that there is significant intrinsic scatter around this abundance gradient, as much as 3 times the systematic uncertainty in the strong line diagnostics. The intrinsic scatter is similar in the nitrogen abundances, although the gradient is significantly steeper. On small scales (deprojected distance < 0.5 kpc), HII regions exhibit local variations in oxygen abundance that are larger than 0.3 dex in 33% of neighboring pairs. We do not identify a significant oxygen abundance gradient among PNe, but we do find a significant gradient in the [N II] ratio that varies systematically with surface brightness. Our results underscore the complex and inhomogeneous nature of the ISM of M31, and our dataset illustrates systematic effects relevant to future studies of the metallicity gradients in nearby spiral galaxies.