Explosive volcanic eruptions, potentially involving large amounts of magmatic and entrained water, are thought to have been very important in the Noachian and Hesperian periods earlier in Mars history, and basaltic plinian eruptions are likely to have occurred throughout martian history. Previous treatments of explosive volcanic plumes on Mars have simply extrapolated plume models for the Earth's atmosphere to Mars. Taking account of known limitations to the applicability of this approach, which suggest that convective plumes may be capable of reaching only 20 km height on Mars, we introduce the concept of inertial plumes, capable of carrying clasts to much greater heights and dropping them into the lower atmosphere over a wide area. Atmospheric circulation patterns guarantee wide dispersal and thick deposits of tephra resulting from both types of eruption. The presence of large amounts of water in convecting explosive eruption plumes can also lead to condensation of water on small particles and the consequent accretion of other particles as the smaller particles fall through the plume, producing accretionary lapilli. Formation of accretionary lapilli significantly alters the spatial distribution and grain sizes of pyroclastic fall deposits from those involving discrete juvenile clasts with negligible clast interactions. We model the eruption and dispersal of tephra, and the formation of accretionary lapilli on Mars under current atmospheric conditions and explore the consequences of this for the geometry and grain size of deposits formed from explosive eruption plumes. We show that explosive eruptions can produce thick widespread deposits of ash and lapilli similar to those thought to have produced mantling deposits in several regions of Mars. We develop a detailed example that shows that local hydrovolcanic explosive eruptions and solely magmatic eruptions originating from the nearby Apollinaris Patera could have emplaced tephra and accretionary lapilli in the Columbia Hills region of the Mars Exploration Rover Gusev site. If the atmospheric pressure was higher early in Mars' history than now, eruptions would have led to somewhat more extensive pyroclast dispersal than under current conditions.