Hydrogen and oxygen are common elements that were widespread during the formation of the solar system. Mix them together and you get water. Most of the hydrogen was lost off the rocky planets early in the solar system's history, but some of it got bound up in rocks ( along with a lot of oxygen) where it could be later released as water