It's not well-explained, and unfortunately I'm mixing up 3.x and 4e rules, I'm sure. Here's how I think it works.
Perception is the more important skill here (or Spot or Listen, depending on which version of D&D you're talking about).
I'm going to describe two simple "parties" here. One are the PCs, and consist of Fighter, Rogue, Wizard and Cleric. Rogue has Perception and Stealth as class skills, no one else does. The other party consists of Bandits (Perception and Stealth) and Outlaws (neither).
Rogue is scouting, and deliberately trying to be stealthy, so he gets to make a Stealth check. None of the other PCs get to make Stealth checks. (In order to make Stealth, you need cover and concealment, and they're walking on the road.) The bad guys are crouching behind some tree stumps on a slope beside the road and so Bandits and Outlaws both get Stealth. (Because Outlaws aren't trained, their scores are poor.)
Make your Stealth checks first! Outlaws roll average on Stealth, Bandits roll well, Rogue rolls well. Each PC makes a Perception check to avoid being surprised. Cleric and Wizard fail their checks against Outlaws (and Bandits). Fighter makes his check against Outlaws but fails against Bandits. All but Rogue fail their checks against Bandits. Bandits and Outlaws should in theory make their Perception checks at this point; they all fail against Rogue but it doesn't really matter, as they saw the non-Stealthy PCs.
Only PCs who failed any Perception checks are surprised. Cleric and Wizard are surprised and don't get to act in the surprise round at all. Fighter gets to act, even though the Bandits made their Stealth checks against his Perception. Rogue gets to act. Because Bandits and Outlaws automatically made their Perception checks against the PCs, they are not surprised (even though they didn't spot Rogue).
Everyone rolls initiative right now, even the surprised PCs.
The surprise round gives only partial actions, which could mean a non-surprised PC might not be able to attack. (For instance, if the Bandits and Outlaws were up a slope, and Fighter doesn't have a bow, he might only be able to partially climb the slope.)
To continue the example, Bandits have bows, but Outlaws don't. The initiative order is Rogue, Bandit, Fighter, Outlaw, Wizard, then Cleric. Rogue won initiative, so he attacks one of the Bandits. The Bandit is still flat-footed against him (or in 4e, the Rogue has First Strike) so the Rogue can sneak attack Bandit. Bandits go next. They can now clearly see Rogue, but think Wizard is a better target, so they shoot him. Wizard takes a lot of damage and drops. Fighter (partial in 3.x) charges up the slope, fighting one Bandit. Outlaws (partial) charge Fighter, as he's the closest target. Wizard can't go, because he's both surprised and unconscious. Cleric can't go, because he's surprised.
First "full" round of combat goes. Rogue Tumbles to where Fighter is standing and tries to flank a Bandit with him. Some Bandits shoot at Cleric, some surround Fighter and attack him. Fighter kills one Bandit. Outlaws mostly attack Fighter (who is now bloodied), but one rushes at Cleric. Wizard is still unconscious on his initiative, and loses a hit point due to bleeding (or failed a death save in 4e). Cleric casts a healing spell on Wizard. (If this were 4e, he wouldn't provoke any sort of opportunity attack if he's close enough to Wizard, and could even use a standard action to attack. If this were 3.x, Cleric would probably provoke from moving toward Wizard and might even provoke by casting the healing spell too!)
Second full round of combat...
I'm glad the OP made this thread. Someone will probably go through my post and correct all those errors, but I think it's a good example. Unlike the "how to run an ambush" sidebar in Keep on the Shadowfell (which was written before the Stealth errata, as if that wasn't confusing enough).
On another note, we should probably make one example per edition.
