Navy showers are short, methodical showers intended to use minimal water. 1-2 gallons of water per shower are possible.
The general process is:
Truck stops have shower available for purchase. These amenities are designed for truck drivers but are available for anyone. Couples can generally shower together for the same price.
Pilot/Flying J have rewards programs where every 14g of fuel accrues credit toward a shower.1) Love's has a similar program but it requires 50g diesel fill-ups, so it will not apply to many 'dwellers.2)