Gradually. Except in very rare circumstances, not every visitor has to see the changes immediately. The main challenge is consistency of the data model, which should be separate from the presentation layer anyway, in an MVC-stylee. If you can upgrade the data model without affecting existing versions of the presentation layer, your presentation layer can be rolled out gradually.
