Establishing the base
You start out in the bottom of a rectangular map, similar to "The New Dominion" but larger in size. The Protoss Temple (the location of which is given to you from the beginning) is on the opposite side of the map, but you don't actually have to fight through all of your way there; once you've destroyed the Protoss that are near your base, it's all empty land until you start getting close to the Temple.
Note your large starting supply of minerals. In addition, you have so much minerals in your large starting area that you could build enough Zerglings to fill the 200 supply limit five times over. The limiting factor is gas; you only get one geyser, and that won't even be close to enough. Therefore, your focus at this stage of the scenario is to secure more gas locations while building up your defenses and climbing the tech tree.
Scout out the general surroundings of your base with Overlords while gathering the resources next to the Hatchery. You'll find a sizable mineral field to the left and another one to the right; also, there are stray minerals near the cliff to the right side, but you can't mine those until the Protoss defenses on the cliff are taken out. As the minerals start coming in, build two more Hatcheries, each near the two mineral fields. Not only will this help you gain resources much faster, it will also come in handy for the mass-production you'll be doing later.
Since what little gas you have must go primarily towards building attack units, Sunken and Spore Colonies will have to handle the defense. Fortunately, these only cost you minerals, and it's not like you'll run out of those anytime soon. The Protoss do attack in fairly large waves (expect Carriers and Reavers from the very beginning), so you need a dense defense network. By the end of the mission, you should have about 50 Colonies defending your base(s); again, you need this many because you need to save the units for attacking. When building static defense, make sure the Colonies are in positions to defend each other—for example, don't build three Sunken Colonies in a location where they can't be covered from air units by Spore Colonies, and try to ensure that any enemy attacking one of your Colonies is fought back by both the one under attack and at least two additional Colonies.
Clearing the lower half of the map
Two Protoss bases lie to each side of your base, and this is where most early attacks originate from. Whacking them will give you a significant amount of breathing room. But more importantly, they have gas geysers! Even if they're depleted, that's still more than what you would be otherwise getting.
Build a force of 24 Zerglings, 12 Hydralisks, and 4 Guardians (Mutalisks are also handy but not necessary). If your Ultralisk survived up to this point, throw him in too. Make sure to upgrade Adrenal Glands for your Zerglings before attacking. It doesn't really matter which base you attack first, but the left side is slightly closer so you should probably go for that one. Lead with the Guardians, destroying everything in sight range (focus on any Reavers you see); Hydralisks should follow closely, ready to destroy enemy air units. When the area around the ramp up to their base is clear of Photon Cannons and units, move in the Zerglings and raze the structures. When the base is gone (and this includes the small area north of the ramp, containing a Templar Archives and some defenses), quickly bring in Drones to morph into a Hatchery and Extractor. Enemy Scouts and Carriers like to harass this location, so be ready with a matrix of Spore and Sunken Colonies.
After sufficient defenses have been set up here, move the same attack force over to the east and repeat the strategy. This base has a Stargate and some Scouts, so bring some Mutalisks to take fire for the Guardians. Otherwise, this one should be easier to attack than the last because there won't be any Reavers.
When you have destroyed both bases and set up your own, you just increased your gas income significantly and cut the Protoss's unit-producing capability even more significantly.
Building an army
Here's what you should do immediately after setting up adequate static defense in the eastern outpost; take your attack force and move it to a location directly north of that outpost (it's not on the same plateau so the ground units have to move down the ramp). You'll find a full Vespene geyser with 5000 gas in it. You could have colonized this location earlier, but it wouldn't have been very viable because of its proximity to the Protoss base. Scout with an Overlord or refer to the screenshots if you can't find it; once you have, build up the static defense like in your other bases.
Now you have six(!) Hatcheries. Use those and the ridiculous amount of resources you should have accumulated by now to build an assault force consisting of two full groups of Zerglings, a full group each of Hydralisks, Mutalisks, and Guardians, 4 Ultralisks, and a handful of Scourge.