The rapid monitoring and accurate estimation of dynamic changes in soil organic carbon (SOC) can make great efforts in understanding the global carbon cycle. Traditional field survey is the main approach to obtain soil data and measure SOC content. However, the limited number of soil samples and the sampling cost hinder the quality of digital soil mapping. This research aims to explore the sensitive of sampling density in digital soil mapping, and then design a suitable soil sampling plan based on a series of sampling indices. Headwall hyperspectral images (400–1700 nm) were used to estimate the SOC map by partial least squares regression (PLSR) and PLSR kriging (PLSRK). Three traditional soil sampling methods (random, grid, and Latin hypercube sampling) with 10 classes of sampling densities (6.26, 2.79, 1.57, 1.01, 0.69, 0.53, 0.39, 0.30, 0.26, and 0.20 ha−1) were designed. The R2, root mean square error (RMSE) and ratio of standard deviation to RMSE (RPD) were used to evaluate the prediction accuracy in digital soil mapping by ordinary kriging. Three new indices, namely, the ratio of sampling efficiency to performance (RSEP), the density of soil samples index and the comprehensive evaluation index of prediction accuracy, were used to select a suitable soil sampling plan. Results showed that (1) the prediction accuracy of PLSRK (RPD = 2.00) was higher by approximately 11.73% than that of PLSR (RPD = 1.79), and the hyperspectral images provided an actual referential SOC map for the study of soil sampling; (2) the grid sampling plan performed better than the random and Latin hypercube sampling methods, and the quality of SOC map improves with the increase of the sampling density, and (3) the computer simulation and field verification indicated that RSEP is one feasible index in designing a suitable soil sampling plan.