In general:
If the ball is caught before it hits the ground, the runners cannot advance from the bases they are on until the moment the catch is made. If they are off the base at that moment, they must return to "tag up", then may proceed to the next base. But, the ball is still live, and the runner has to beat the throw and/or avoid the tag. Note, if the runner is caught waaaaayyyyyy off the his original base, he can be put out at his original base, on a FORCE play (the fielder need only touch the base, with the ball in his possession, before the runner touches it). But if he successfully tags up and is headed for the next base, or back to his original base, the play must be a non-force play (the fielder must "tag" the runner, i.e., touch the runner with his glove, with the ball inside it, before he reaches either base.
If the ball is NOT caught in the air, everything proceeds the same way as if the ball was a grounder. This can be bad for the runner because, if he's EXPECTING the ball to be caught, he has to hang around on or close to his original base until the fielder misses the ball. This greatly reduces the amount of time he has left to make it to the next base. And if he's on first, or if he's on any other base but all the bases behind him are full, he HAS to go to the next base.
Note that, if there are two outs before the fly ball is hit, the runners need not "tag up", because, if the ball is caught, the inning is over anyway, and if the ball is not caught, it's the same as a ground ball.
Somewhere back in the history of baseball, a clever fielder figured out that, if there were multiple runners on base in a "force-out" situation (for example, first and second), and less than two outs, and a pop-up was hit to somewhere on the infield, the fielder could INTENTIONALLY MISS THE CATCH, then pick up the ball and get a double play fairly easily, because all the runners had to hold up to see if the ball would be caught. That was why baseball came up with...
The Infield Fly Rule.
If there are runners on first and second, and less than two outs, and a fly ball is hit in such a manner that it is catchable by an infielder, the umpire calls the rule into effect, loudly informing all players while the ball is still in the air. The batter is automatically out, wether the ball is caught or not. This removes the force condition on the two runners and prevents the fielder from turning an easy double play. If the ball is caught, runners may still tag up and proceed to the next base (though they are very unlikely to make it, given that the ball is already in or near the infield). If the ball is not caught, it is considered the same as the batter grounding out, and runners can advance if they choose, without tagging up, but they don't have to (and, once again, they're not likely to make it if they try, because the ball is already in or near the infield).
Usually, what happens is that, as soon as the umpire determines that the rule is in effect, and alerts the players, the runners go back to their original bases and sit tight. Though he doesn't have to, the fielder ALMOST ALWAYS catches the ball, either as a matter of pride, or because it's easier than bending over to retrieve a ball on the ground. The runners make no attempt to advance, and the fielder throws the ball back to the pitcher, which ends the play. The resulting situation is exactly the same as it was before, except that there is one more out on the scoreboard, and a new batter is up with an empty count.
--------------------------------------------------------------------------------
For a base runner to advance on a caught fly ball, the runner must be in contact with the base he/she was occupying at the time of the pitched ball when the catch is made. Once the catch is made the runner may attempt to advance. If the runner attempts to advance before the fly ball is caught and is ruled to have advanced to the next base safely, the defensive team may make an appeal to the umpires that the runner left the base before the catch was made. This appeal must be the first order of business after the play and is made by:
1) The defensive team notifying the umpires of their intent to appeal.
2) The pitcher taking his normal stance on the pitching rubber with the ball.
3) The pitcher steps off the rubber and throws to a fielder who is in contact with the base that the runner left too early.
If the umpires disallow the appeal, the runner stays at the base he/she currently occupies. If the umpires allow the appeal, the runner is out. If this out is the third out and the runner who was called out by the appeal had scored, the run is disallowed. If this out is the third out and a runner who was ahead of the runner called out by the appeal had scored, the run is allowed.
It is not the umpire's responsibiity to make this call. This appeal must be made by the defensive team.