This behavior has little to do with using a carbonated beverage. Try search terms butane water rocket to see plenty of other examples of this.
The phenomenon that is happening is the large volume difference between liquidus and gaseous butane (with maybe some $\ce{CO2}$ to boot) forces the dense liquid water out of the vessel at a high pressure, and Newton's First Law takes care of the motion of the plastic bottle relative to its liquid contents.
The Steps:
Adding butane
When the butane is introduced into the container, it is an expanding vapor, which loses some energy from the expansion. Butane condenses into a liquid at about $0°\!\mathrm{C}$, and so when you add butane from the compressed can some of it condenses into the liquid from the heat loss due to expansion, aided by contact with the presumably cold (but still $>0°\!\mathrm{C}$) surface of the cola. Butane's density is about $0.6\,\mathrm{g}\,\mathrm{cm}^{-3}$ and so it floats on top of the sugar solution.
Releasing the container
When the vessel containing the two liquids (cola on bottom, butane nearer the mouth) is inverted, the (relatively) warm water (or cola, or otherwise) comes in intimate contact with the liquid butane. The high surface area of the interaction causes the temperature of the butane to be immediately raised above $0°\!\mathrm{C}$, and is given plenty of energy to enter the gas phase. In the case of cola, I suppose it is possible that during all of this, droplets of butane are providing nucleation sites for $\ce{CO2}$ as well, but as the whole effect can be shown to happen with water, it is rather beside the point.
The change in volume
As mentioned, the density of liquid $\ce{C4H10}$ is about $0.6\,\mathrm{g}\,\mathrm{cm}^{-3}$, so with a molecular weight of about $58\,\mathrm{g}\,\mathrm{mol}^{-1}$ and an ideal gas volume of $22.4\times10^3\,\mathrm{cm}^3\,\mathrm{mol}^{-1}$. Each $\mathrm{mL}$ of butane contains about $0.01\,\mathrm{mol}$ of $\ce{C4H10}$, and the liquid butane will expand to $230$ times the volume of the liquid that is added initially (using ideal gas approximation). If the liquid is about $1\,\mathrm{cm}$ deep and the diameter of the bottle is about $7\,\mathrm{cm}$, that is about $40\,\mathrm{cm}^{3}$ liquid, or about $10\,\mathrm{L}$ of gas.
If we take a look at the answer to another question about soda, we see that there is about $0.14\,\mathrm{mol}\text{ of carbon dioxide per }\mathrm{liter}\text{ of soda}$, and so if all of the $\ce{CO2}$ is released simultaneously (like the memetic Mentos example), it adds about $3\,\mathrm{L}$ of gas to our expansion.
The upshot:
The gas is aching to get out of the cola bottle, however now the liquid in the inverted bottle is standing between the gas and its equilibrium (atmospheric) pressure. The liquid, being a fluid, is forced out of the mouth of the bottle. Presumably the user had a loose grip on the vessel, which is then propelled in the opposite direction from the liquid plug with the equal and opposite momentum. For reference, since conservation of momentum states $\mathrm{\mathbf{p}} = 0 = m_1\cdot\mathrm{\mathbf{v_1}} + m_2\cdot\mathrm{\mathbf{v_2}}$ a $10\,\mathrm{g}$ soda bottle would travel fifty times faster than $500\,\mathrm{g}$ of liquid it is being forced to release, as in a partially empty bottle of cola.
Referring to the Wikipedia article on Water rockets, pressures from bike pumps ($75\,\mathrm{psi}$) and air compressors ($\mathop{>}200\,\mathrm{psi}$, said to be dangerous) are used to launch this type of rocket. Since we are starting from a non-enclosed vessel, we wouldn't really have static pressure but the $13\,\mathrm{L}$ of gas that we are generating (at final pressure $1\,\mathrm{atm}\approx 14.7\,\mathrm{psi}$) would have some equivalent. If confined to say, a $250\,\mathrm{cm}^3$ headspace, this would correspond to something like $750\,\mathrm{psi}$ to $1000\,\mathrm{psi}$!
