We present results of mid-infrared spectroscopic mapping observations of six star-forming regions in the Small Magellanic Cloud from the Spitzer Spectroscopic Survey of the SMC (S4MC). We detect the mid-IR emission from polycyclic aromatic hydrocarbons (PAHs) in all of the mapped regions, greatly increasing the range of environments where PAHs have been spectroscopically detected in the SMC. We investigate the variations of the mid-IR bands in each region and compare our results to studies of the PAH bands in the SINGS sample and in a sample of low-metallicity starburst galaxies. PAH emission in the SMC is characterized by low ratios of the 6-9 micron features relative to the 11.3 micron feature and weak 8.6 and 17.0 micron features. Interpreting these band ratios in the light of laboratory and theoretical studies, we find that PAHs in the SMC tend to be smaller and less ionized than those in higher metallicity galaxies. Based on studies of PAH destruction, we argue that a size distribution shifted towards smaller PAHs cannot be the result of processing in the interstellar medium, but instead reflects differences in the formation of PAHs at low metallicity. Finally, we discuss the implications of our observations for our understanding of the PAH life-cycle in low-metallicity galaxies---namely that the observed deficit of PAHs may be a consequence of PAHs forming with smaller average sizes and therefore being more susceptible to destruction under typical interstellar medium conditions. ; Comment: Submitted to ApJ