Paraffin wax should be stored in a cool, dry place away from direct sunlight and heat sources to maintain its quality and prevent melting.