It's a glitch.
Take a boat or plane (or car, with the Flying Cars cheat) and head to either the southwest or southeast corner of the map. The player then flies or drives out to sea in a south-western or south-eastern direction. This glitch takes a while so it is suggested that the player tape down the button and leave the game running. 30 real-world minutes should be long enough. Once the player is sure that all territories have been unlocked they can either fly or drive back (again, takes a long time) or drown themselves in order to get back immediately.
If done correctly, there should now be multicolored territories in the Badlands, San Fierro, Las Venturas, and the desert. However these territories are still only owned by Ballas and Vagos, the multiple colors are somehow caused by combinations of these wherever the "lost" territories overlap.
All unconquered "lost" territories will act much like they did before the glitch was activated, however there will be Ballas or Vagos wandering around them whereas in an unglitched game many of these areas would not normally harbor these gangs.
All these can be conquered by starting a turf war with the resident gangs, and are taken over after only one wave.
One downside that some players dislike is that once the area becomes theirs it will be ruled by Grove Street Family members; this means that people driving by will have the Grove Street Families' favorite cars, rather than the specific types usually found in that area before being conquered. This means the variety of jackable rides is significantly reduced.