Sand People Enclave
Objectives: Either persuade the Tuskans to cease attacking the Sandcrawlers, or kill them all
Once you're inside the enclave, you can have HK-47 translate for you. The Light side dialogue choices are fairly obvious here, but just be sure you don't accidentally let HK-47 decide what to say - he's a little trigger happy. After a short conversation, you'll be sent back to Anchorhead to find some moisture vaporators. Otherwise, you can go hostile to the Tuskans and kill everyone to find what you came for: the Tuskan Chief's gaffi stick, which you'll have to show to the protocol officer in the Czerka office back in Anchorhead to finish off this quest. Don't miss the Jawas back in the back; these are the tribesmen that Iziz was asking about earlier.
If you decide to help the Tuskans (you'll probably want to use the handy map screen warping tool to jump back to Anchorhead), you'll find that the Czerka protocol officer isn't very interested in your nonviolent solution to the Tuskan problem. Luckily, the Rodian behind the counter is a bit more sympathetic, and will part with a couple of moisture vaporators if you ask him for something specific. Grab them, and head all the way back out to the Sand People enclave.
Once you're there, have HK-47 talk to the guard at the gate; you'll be escorted inside and given another audience with the Chieftain. As long as you play it straight, you'll get everything that you want: the Chieftain's gaffi stick, the Jawa captives, and the ability to look around the enclave. Also, be sure to ask him about the Star Map. One of the rooms to the northeast has some fairly decent items in it, including some heavy plating for HK-47. Don't worry about the rest of the wicker baskets; they mostly contain grenades, and you won't be able to access them without the Tuskans becoming very upset.
Bring the Chieftain's gaffi stick back to the Czerka office for your reward. You can also talk to Iziz by the gates to finish off the Fair Trade quest, assuming you rescued the Jawas. If you missed the East Dune Sea map, either due to not asking the Chieftain about the Star Map, or because you killed him, Iziz will give you a copy of it, so head back out to the vicious wastes and proceed to the East Dune Sea, making sure you have some bantha fodder in your inventory before you do so.
Eastern Dune Sea
Objectives: Investigate the krayt dragon rumors
The eastern portion of the Dune Sea is fairly uninteresting; nothing to see except bantha, dewbacks, and the odd Twi'lek standing in front of a massive cavern. Run over to the cave to watch a little cutscene; you can get close to the cave to see the krayt for yourself, but don't go in. Oh, all right, you can go in if you want. Just make sure you save your game first.
When you're done screwing around, talk to Komad at the cave's entrance. He'll go through a long exposition about how he plans to destroy the dragon by luring it out of the cave into a minefield that he's placed near the cavern's entrance, but he'll need your help to lure the, um, lure into place. It's quite an alluring plan, really.
You did bring bantha fodder, didn't you? If not, you'll need to schlep all the way back to town and get some from the merchant in the spaceport. If you did bring it, just walk up to one of the bantha on the high plains to start it walking towards the cave. The Tuskans will attack, but don't let Komad's fearmongering affect you; they're just Tuskans with blasters. Nothing to worry about unless you plan on podracing through here later on. Dispatch them back to the bosoms of whatever desert gods they worship, then talk to Komad again.
And the other shoe...doesn't fall this time. The plan works, the krayt dragon dies an explosive death, and Komad offers you a reward. This is one time you don't want to be all altruistic and virtuous; we're not talking credits here. You'll receive a krayt dragon pearl for your troubles; use it in a lightsaber to get +2 damage and +3 attack. This is a valuable object, so be sure you pick it up. You can also demand more of the reward and kill Komad for a Dark side shift, but he still only carries one additional pearl, in addition to a couple of grenades.
Head into the cave, checking the bodies and the rubble for items. If you've obtained Bastila's side quest, you'll find her father's holocron next to the Star Map. Get the Map, then head back out of the cave. If you killed Calo Nord earlier, you may run into Darth Bandon here (see the Galaxy Side Quests section for more on Darth Bandon).