In general, Gestalt characters are more durable than their normal counterparts, and have better endurance.
They aren't overly more powerful.
In general, if everything else is "standard" (WBL followed, 4 level appropriet encounters per day, et cetera):
If the beasty you're throwing them against relies on attacks with saves (e.g., a CR 7 Medusa) use things at +2 CR compared to what you'd use against a "normal" party (so a Medusa would be an appropriet challenge for a gestalt party of four 5th level characters).
If the beasty you're throwing at them relies mostly on things without saves (e.g., a CR 7 Hill Giant) use things at +1 CR compared to what you'd use against a "normal" party (so a Hill Giant would be an appropriet challenge for a gestalt party of four 6th level characters).
Warning:
Occasionally, a beastie's challenge rating is loosly based around the spell level of the counter; if for whatever reason, the counter isn't available (because it is a few spell levels away, perhaps), the beastie's effective CR goes up.
Also:
Not all combinations are created equal; some amount of min-maxing is required to prevent gimping a character. It's usually much more effective if you have a "primary" class that fills the role you want the character to have, and a "secondary" class that covers its weaknesses - so you can have a Sorcerer/paladin that focuses on spells with attack rolls and ranged combat (essentially giving up armor proficency and Smite in favor of spellcasting) or a Paladin/sorcerer that focuses on Still Spell and personal buffs (essentially giving up zappy type spells in favor of melee). The Paladin/Sorcerer that tries to be a full caster and a full meleer will have issues (stat distribution, ASF, et cetera).
A couple of suggestions for requirements of your players final build:
At least 2 good saves (no Wizard/Sorcerers, please).
At least d8 HD.
At least one side must be a full "caster" (Druid, Cleric, Wizard, Sorcerer, Psion, Wilder, et cetera - 9th level spell type abilities) to reduce the builds that are easily eclipsed by "magic".