Note, going to the Gym is also a great way to put on weight, so, I wouldn't correlate "going to the gym" and adding/losing weight. There's good research that shows even high-metabolic activity like running 5 miles/day isn't correlated with losing weight (though it is well correlated with increased aerobic capacity).

Basically, any diet whatsoever will result in you losing weight. Just measuring/charting your weight is effective too. Chewing 7 times with every bite will do it.

High protein diets are particularly awesome for a number of reasons though - in the first couple months you drop a ton of water, which makes the scale drop quickly, which is emotionally rewarding. And, eating a lot of protein tends to result in more rapid satiation. (Water and Dietary Fiber are good here too - so a simple diet trick is, four glasses of water with every meal).

Protein is also good when you are lifting, so is an important component in building muscle mass...