I don't follow it myself, but the Clean Eating books by Tosca Reno are very clear and easy to understand and seems to work well for a lot of people. I believe that truly following the clean eating style and working out with weights and doing cardio are some good fundamentals to getting leaner. If the lower fat eating is not for you, I would personally recommend a lower carb approach like Atkins or Primal (a modified Paleo diet with allowances for higher fat meats and small amounts of high fat dairy like cream and butter, and more fruits and veggies than Atkins).
I can't really address how to get cut more than this , getting cut happens after you significantly reduce your body fat AND have built muscle.
As you have already discovered, working out just can't over ride bad eating, and you have to be careful that you don't succumb to the feelings that working out gives you a license to eat more.
How many times per week are you working out? Working out any times per week is great, but to start to see changes, you should really be working out at 5-6 days per week on most weeks, using both cardio and weights. Since you are just starting out, your weight days can/should be full body workouts instead of split routines, alternating with cardio days. You could also try out circuit training where you combine weights with cardio bursts.
Does the Y offer trainers? I would highly suggest hiring a trainer for at least 3 sessions to put together some workouts for you, but even better if you can do more. Personally I used a trainer for the better part of 2 years before venturing into the world of at home fitness, it was probably the best money I ever spent.
