Basic strategy was putting something in front of them that can redirect to the new system upon a trigger. Let's assume its functionality + tons of data. The new system first gets the data moved to it in batch form for efficiency reasons. Once it catches up enough, it starts syncing in a more online fashion until it gets to point that it's syncing in real-time. All kinds of tests are performed on that system throughout this process. Eventually, a change-over happens that should be barely perceptible. The inability to do this is usually due to fragile architecture or tightly-coupled implementations which are unfortunately all too common in enterprises.
Note: It can also help if your app was written in something like Common LISP or Erlang that supports live updates. That with the delta approach (version A->A/B->B) equals upgrades with no downtime. ;) Combining it with clustering approach is quite powerful but clustering approach is more applicable to tools majority uses.