Chambero -- In parts of Nevada, New Mexico and Arizona and to some extent in the desert areas of California, BLM grazing permits in many of these areas are attached to "water base property," while in most of the rest of the West, the grazing permits are attached to land "base property." When the states were admitted to the Union under their individual enabling acts, each state received anywhere from 2 to 4 sections of land per township, but the federal government kept title to areas that had not been homesteaded, claimed under the General Mining Law, deeded to the railroads, or claimed under some other law allowing private claims. The several homestead acts, including the Desert Land Act of 1877 provided that the water was severed from the public domain and subject to appropriation under state or territorial law. The homesteaders only received a patent to land from the federal government and had to appropriate their water rights under state law if they wanted to irrigate their homesteads. States and their predecessor Territories recognized the prior appropriation doctrine from early on and people were able to secure their rights through claims and filing systems set up by the States and Territories.
The desert states, unlike the other Western states, allowed for the appropriation of water for various purposes solely in the appropriator's name, including livestock grazing, even if the appropriator did not have title to the land. Thus, there are many water rights on federal and state land that are held by private individuals and entities. The BLM then recognized water base properties for issuance of grazing preferences (based on a system of recognizing prior grazing use of the area, ownership of water rights, proximity of the headquarters to the area, etc.) in these desert areas. This is how Bundy owns water rights on federal lands. Fortunately for Texas, it has a way different history and doesn't have to put up with having the federal government own 40-90% of its land area.