There seems to be a little confusion on this in the other answer, even though it was accepted already, so I'll attempt to clear that up.
- Rivali's Gale - 6 minutes
- Urbosa's Fury - 12 minutes
- Daruk's Protection - 18 minutes
- Mipha's Grace - 24 minutes
Note that all except Mipha's Grace have 3 uses before the cooldown comes into effect.
These times correspond to the day-night cycle of the game. The game's clock runs one minute for each second in real-world time, so the game has a 24 minute day-night cycle. Each of the powers correspond to 1/4, 1/2, 3/4, and 1 full day to recharge. Fast forwarding by sitting by a fire or sleeping in a bed does not speed this along.
Update for how the Champion's Ballad DLC changed things
The DLC will allow you to unlock story missions related to each of the divine beasts. The completion of each Champion's quest will cause their power to decrease to 1/3 the original time, so the new cooldown times are:
Rivali's Gale - 2 minutes,
Urbosa's Fury - 4 minutes,
Daruk's Protection - 6 minutes,
Mipha's Grace - 8 minutes