We identify sources with extremely hard X-ray spectra (i.e., with photon indices of Gamma<0.6 in the 13 sq. deg. NuSTAR serendipitous survey, to search for the most highly obscured AGNs detected at >10 keV. Eight extreme NuSTAR sources are identified, and we use the NuSTAR data in combination with lower energy X-ray observations (from Chandra, Swift XRT, and XMM-Newton) to characterize the broad-band (0.5-24 keV) X-ray spectra. We find that all of the extreme sources are highly obscured AGNs, including three robust Compton-thick (CT; N_H > 1.5e24 cm^-2) AGNs at low redshift (z<0.1), and a likely-CT AGN at higher redshift (z=0.16). Most of the extreme sources would not have been identified as highly obscured based on the low energy (<10 keV) X-ray coverage alone. The multiwavelength properties (e.g., optical spectra and X-ray/MIR luminosity ratios) provide further support for the eight sources being significantly obscured. Correcting for absorption, the intrinsic rest-frame 10-40 keV luminosities of the extreme sources cover a broad range, from ~ 5 x 10^42 to 10^45 erg s^-1. The estimated number counts of CT AGNs in the NuSTAR serendipitous survey are in broad agreement with model expectations based on previous X-ray surveys, except for the lowest redshifts (z<0.07) where we measure a high CT fraction of f_CT^obs = 30 (+16 -12) %. For the small sample of CT AGNs, we find a high fraction of galaxy major mergers (50 +/- 33%) compared to control samples of "normal" AGNs.