We present a search for all embedded protostars with internal luminosities < 1 solar luminosity in the sample of nearby, low-mass star-forming regions surveyed by the Spitzer Space Telescope c2d Legacy Project. The internal luminosity (Lint) of a source is the luminosity of the central source and excludes luminosity arising from external heating. On average, the c2d data are sensitive to embedded protostars with Lint > 4E-3 (d/140 pc)^2 solar luminosities, a factor of 25 better than the sensitivity of IRAS to such objects. We present selection criteria used to identify candidates from the Spitzer data and examine complementary data to decide whether each candidate is truly an embedded protostar. We find a tight correlation between the 70 micron flux and internal luminosity of a protostar, an empirical result based on observations and two-dimensional radiative transfer models of protostars. We identify 50 embedded protostars with Lint < 1 solar luminosities; 15 have Lint < 0.1 solar luminosities. The intrinsic distribution of source luminosities increases to lower luminosities. While we find sources down to the above sensitivity limit, indicating that the distribution may extend to luminosities lower than probed by these observations, we are able to rule out a continued rise in the distribution below 0.1 solar luminosities. Between 75-85% of cores classified as starless prior to being observed by Spitzer remain starless to our luminosity sensitivity; the remaining 15-25% harbor low-luminosity, embedded protostars. We compile complete Spectral Energy Distributions for all 50 objects and calculate standard evolutionary signatures, and argue that these objects are inconsistent with the simplest picture of star formation wherein mass accretes from the core onto the protostar at a constant rate.