Clearly there are a lot of different potential solutions to this depending on the application and design approach. Also, as is clear from the video, bipedal robots are still a long way from achieving the level of elegance in walking that most humans manage with little conscious effort.
As the most important comparison is with humans, it's worth looking at how humans maintain balance. This can involve a lot of senses working in concert.
A key organ is the set of tubes in the inner ear, which is essentially a set of accelerometers. Humans also have an innate sense of where our limbs are in space in addition to a fairly refined sense of both external pressure and exactly how much force our muscles are providing.
Clearly sight is also very important, not just for sensing obstacles but in providing a reference point for speed, position and orientation.
Another very important factor is that the human body has a lot of degrees of freedom and hundreds of different muscles that can act as springs and dampers as well as actuators. Indeed, this is one of the big challenges in humanoid robot walking. Although it's not to difficult to assemble the main joints (e.g. hips, knees and ankles) and provide them with pairs of pneumatic pistons, in real humans the whole body is involved in maintaining balance with constant, subtle and dynamic adjustments in stance to adjust the centre of mass.
In terms of the actual mechanism of the control system it's fairly clear that a human brain is a very different thing from conventional software control. One of the big challenges is that, unlike something like steering a car where a certain control input gives a known response, with walking the whole geometry of the system is constantly changing and the input required might be the sum of a large number of different muscles, indeed there might be a large number of possible inputs to achieve the same output.
With this in mind there are a number of approaches to control. The first is what you might call a 'brute force approach' where you have many sensors and a lot of computing power to model the whole system as a series of free body diagrams and try to model the whole system in sufficient detail that PID control can be effective. But as already mentioned the obstacle here is that the response required for a given correction may be ambiguous.
Another approach is to come up with a algorithm that responds to certain conditions in certain ways with a more limited degree of feedback-based control, i.e. you have a predetermined 'standard' gait and make corrections if something goes wrong.
A third and potentially more powerful method is to use an evolutionary learning type approach where you give the software access to the sensors and actuators and establish some criteria for 'success' and just let it get on with it by trial and error. In this case the software develops control systems pretty much at random and tries them out, deleting the versions which have low success scores and randomly combining the ones that work better.