One-gap is generally a more aggressive attacking defense. Basically, you decide what you are going to do, and you do it.
Two-gap is generally a more controlling defense. You read what the opposing offense is doing and react to it.
In a one-gap, you are forcing the offense to try to block you, if they want. The downside is you may shoot the wrong gap and leave an opening.
At the DL level, one-gap is a bit more about speed and athleticism - to blow through a quick opening or block. Two-gap is more about power and technique, controlling the OL to prevent an opening to either side.
To stereotype, one-gap is more effective rushing the passer. You are going after the QB, or getting into the backfield - just try to stop it. Two-gap is more effective stuffing the run, by controlling the holes the running back can use. You want to shut down all the holes between the tackles, force the run east-west, and let the OLB's or safeties run the back out to the edge without allowing him to gain any forward momentum.
While the Patriots have played some 4-3 over the years, they have generally been less effective. Last year they were very poor in the 4-3 formation.
One can perhaps best point to the Philadelphia Super Bowl as an effective use of the 4-3, but I looked at it much more as a 2-5. The Pats base package included two DL and Vrabel, Bruschi, Phifer, McGinest, and Johnson or Colvin, with Vrabel and McGinest lining up on the edge of the line, sometimes dropping into coverage, sometimes containing the pocket, sometimes rushing McNabb.
The Pats 3-4 two-gap defense has excelled when there are two OLB's capable of rushing the passer, setting the edge against the run, and dropping into coverage - exceedingly versatile requirements. Vrabel was excellent at this, McGinest was very good for a while, Colvin was much more one-dimensional, and Thomas has the capability but has been inside or injured a bit. Obviously the concern of many on this board has been the failure to develop a versatile three-way OLB like Vrabel at his peak.
A two-gap front seven allows those outside linebackers to act in unpredictable ways, taking away what the offense wants to do. A 4-3 is often much more predictable - it is harder for a hand-down 4-3 DE to drop into coverage. The zone blitz is the solution to this, but can be defeated like any blitz with a quick pass to the open receiver, covered by a far less agile down lineman.
Seau and Bruschi have been very effective inside a two-gap system by rapidly reading the play and shooting the right gap to get into the backfield. Almost like free-lancing in a one-gap system, they could immediately understand the play and take a direct route to the ball-carrier. Mayo last year made a lot of tackles, but fewer behind the line because it took him longer to diagnose the play, understand what everyone else was going to do, and then react to his role.
But with the front seven working together with quick diagnoses, the two-gap can be pretty effective at penetrating the backfield and rushing the passer as well as stuffing the run.