Although surface-enhanced Raman spectroscopy (SERS) can rapidly identify molecular fingerprints and has great potential for analysis, the need for delicate plasmonic substrates and complex laboratory instruments seriously limits its applicability for on-site detection. This paper describes the development of an inexpensive aluminum nanoparticle (AlNP)-decorated paper that functions as a facile SERS-based detection platform (Al-PSERS). Polydopamine-protected AlNPs were chemically synthesized and then simply drop-cast onto a hydrophobic cellulose paper, forming a monolayer AlNP cluster array. Because of the abundance of hot spots arising from the plasmonic clusters, the inherent quasi-three-dimensional structure of the cellulose fibers, and the concentration effect of the hydrophobic surface, the Al-PSERS provided significant enhancements to the signal of various analytes, measured using a portable 785 nm Raman spectrometer. Near-field optical simulations and experimental spectroscopic results revealed that the local electric fields and corresponding SERS signal intensities of the AlNP array exhibited clear particle-length and cluster-size dependencies. Therefore, the Al-PSERS could be optimized to provide high sensitivity (enhancement factor: 2 × 103) and excellent reproducibility (variation: 8.72%). Moreover, the optimal Al-PSERS was capable of detecting colorants and environmental pollutants; for example, the detection limits of allura red and benzo[a]pyrene reached as low as 3.5 and 0.15 ppm, respectively. Furthermore, the Al-PSERS could rapidly identify illegal (rhodamine B) and edible (allura red, erythrosine) colorants from a mixture of multiple colorants or from adulterated candies. Because it facilitates rapid detection, is of low cost, and has minimal technical requirements, Al-PSERS should be applicable to on-site detection in, for example, food inspection and environmental monitoring.