Cleaning your paella pan is easy when you follow the following simple steps. Start with scrubbing the pan clean and then using hot soapy water to wash it. Where necessary, you can soak the pan to let the grime loosen a bit. Rinse the pan thoroughly. Coat the pan with fresh oil before storing it in a dry place.