As you suggest, Newton's third law is at work here: the bottle pushes some its water downward and the water responds by pushing upward on the bottle, propelling the bottle upward. In that respect, the water-bottle rocket is like any other rocket. All a rocket needs is fuel and energy. Pushing the fuel backward is what propels the rocket forward-action and reaction. Energy is what allows the rocket to push that fuel backward. In many rockets, the fuel and the energy source are the same thing. Chemical reactions in the fuel release energy and this energy allows the rocket to push the fuel backward.
However, the water-bottle rocket uses two separate materials as fuel and energy source. The fuel is water and the energy source is compressed air. Having water as the fuel makes sense because water is dense and provides lots of inertia for the rocket to push against as it throws water backward out its tail. Having the compressed air as fuel is a good idea because it has little weight for the amount of energy it stores and doesn't load down the rocket.
At launch, most of the water-bottle rocket's mass is water. And with air packed tightly inside, the rocket has lots of energy. When you finally let water start streaming out of the bottle, the compressed air pushes downward hard on the water and the water pushes upward hard on the compressed air. The air conveys this upward force to the entire bottle and up it goes.
Answered by Louis A. Bloomfield of the University of Virginia