One of the priority environmental pollutants, because of its high toxicity and persistence, are the polycyclic aromatic hydrocarbons (PAHs). PAHs are recalcitrant compounds exhibiting high hydrophobicity and therefore readily absorbed in the gastrointestinal tract of mammals, also having a rapid distribution in a variety of tissues with a marked tendency to fatty deposits. Because of its importance as environmental pollutants, soil contamination with PAHs is a priority environmental issue. In recent years, there have been great advances in the understanding of the mechanisms of degradation of PAHs and the techniques for the monitoring of these processes in polluted soils. However, the validation and performance of a bioremediation strategy should be based not only on the effect of the microorganisms in soil (biodegradation of the contaminant), but also in the detection and monitoring of the inoculated microorganisms. This review presents an overview of the strategies for the bioremediation of soils contaminated with PAHs, focusing on the molecular biology methods that can be used for the monitoring of these soils in the field.