Approaches using machine learning methods were investigated systematically to determine the internal quality parameters of Newhall navel oranges based on near infrared (NIR) spectroscopy. Each stage of the approach was investigated extensively and with full comparison. To ensure credibility and robustness, a much larger sample set than previous studies was obtained. Furthermore, the prediction performance of three kinds of NIR spectra (equatorial surface spectra, distal end surface spectra and juice spectra) were evaluated and compared. By using an optimal machine learning approach, all three kinds of spectra yielded promising results for quality measurements. The obtained results were better than that in most previous studies. The equatorial surface spectra performed slightly but consistently better than the distal end spectra. The juice spectra performed best in predicting most internal quality parameters. But in predicting the vitamin C content, the juice spectra performed worse than the surface spectra, which indicated that the prediction with NIRS might result from indirect factors.