In the first area, go right, then down. The sandy bit to the right here doesn't lead anywhere, so follow the path around the bottom. Whilst you're here, set Pound to whatever space Whirlwind is set to.
When you reach a poundable pillar, Pound it in. The chest on the other side contains a useful Guardian Ring - equip it on Sheba. Carry on north to the next area. If you spent any real time in Madra you'll notice that the Madran mayor, Town Elder, and various others are trying to navigate the desert, to no avail. You, however, are more equipped to do this. Follow the path to the south to enter a new area.
This area is quite large and there's a Jupiter Djinni to be had. Pound the first pillar you come across. Keep going right, ignoring the pillar to the north and the two sticking out on your path. When you reach the next one above you, Pound it. Go up and back to the left to pick up an Antidote from the chest. Now, there's a visible difference with the wall behind a pillar, so Pound the first one you saw up here. A wall you can climb is behind it, so get up onto the ledge. Go to the left and hop across the pillar. Go down, and hop across the next one. Here, use the two of them to get across, and finally the last one, to reach Blitz. You'll have to fight it.
Use the groove to slide back down, then Pound the pillar next to it. Head right here until you reach another groove. Slide down this one and exit the area to the right. In this area, pick up the Psynergy Stone and pound the middle pillar. Climb up the wall behind it and go north. In the next sandy bit, there'll be a lump moving around continuously under the sand. You'll notice there's a raised Pound pillar on its path - you need to pound it in so that when the lump - which turns out to be a rather large scorpion - gets there, it turns and leaves the area via the exit. This is why you set Pound to L or R. You don't need to time this first one though.
In the next area, you need to, however. Pound the pillar in once the scorpion has been past going upwards. If you do it when it's about to go upwards, it'll get caught in an endless loop, and you'll have to leave the area to reset the pillars. In the third area, you need to Pound the right-hand pillar when it's going to come downwards - if it helps, watch its cycle a few times so you know when you have to Pound. If you do it correctly, the scorpion will get directed into a sandy area surrounded by rocks. If you want, set Djinni on standby ready for summoning, and heal as well. When you're ready to rumble, follow the scorpion onto the sandy area. It'll jump out, and use Scoop on the sand, and it'll collapse. It'll jump in after you, starting the battle.
Boss Battle: King Scorpion
One way of approaching this battle is to have your two Mercury Djinni (who would probably do best to be on Jenna) set to Standby, as well as Felix's Iron and Sheba's Ether and Breath. This way, the first turn, Felix can unleash Echo, Jenna can use Nereid and Sheba can use Flora. Next turn, Ragnarok from Felix, Jenna unleashes Cannon and Sheba unleashes Blitz. Felix should either be unleashing or using Ragnarok for the rest of his turns, Jenna doing the same, and Sheba either using Summons or healing (with items if possible). The King Scorpion only has 1000HP which means he shouldn't last that long, especially since you should be dealing about 60-100 damage a turn (Flora does about 200).
Once it's over, equip the Scoop Gem on Felix and use Scoop on the sandy circle in the middle of the cave. Now that you're out again, head back to the area where the Madrans are (you'll need to use a groove since you can't Pound things lower than you). When you reach the bit where you slid down a groove in the first place, use Pound on the pillar and climb up the wall behind. If you go pretty much directly left you'll come across a similar sandy circle. Use Scoop here to uncover a ladder. Go through the cave (it's quite short) and when you come out the other side, climb up the walls. The Madrans will notice you up there and will conclude a path must have opened somewhere.
Keep going. The next area has a load of sandy circles, one of which contains 315 coins. Go into the cave ahead. There are a lot of fast-moving sand currents here - you need to navigate them. For the first bit, get to the very top and run across the sand current flowing downwards. Hop back on at the bottom and get off in between the rocks to reach a chest containing a Hard Nut. Use this on whoever has the lowest Defence. Get back across, and then go upwards (the spaces in between the rocks are big enough to allow you to run across without losing too much ground). When you reach the top, get off on the square surrounded by rocks with a Pound pillar near. Use Pound here, then go past it after stepping on the current again. The chest here contains a Blow Mace, a good weapon for Sheba.
Let the current carry you down again, and get off on the right where you can. If you miss any of these you'll have to go all the way around again. When you get off, go down the ladder and exit the cave. There are sand waterfalls here - you can either let either of the two you can get to carry you off the ledge or use the climbable wall. Either way, at the bottom run northeast, use Reveal on the 3x3 square of rocks, open the chest (containing a now-useless Lucky Medal; save it as it will become very useful later on) and climb the wall on the far right. Run across the two sand waterfalls here and use Lash on the rope. Let this waterfall carry you down, but stay on the right-hand side - if you don't, you'll get caught behind the rocks. If you get it right, you can get off the right side of the waterfall and grab a Trainer's Whip from the chest (oooh, kinky!). Let the waterfall carry you off and go back to the right.
Run across these two sand waterfalls again, and climb the wall. Go around the top of the left-hand waterfall, and let the right-hand one carry you on top of the rocks below so you can exit the desert. You can go south here but it leads to a one-way sand waterfall - leading back to Air's Rock. So go northeast, out of the desert. On the world map, head north to enter Alhafra.