1. Every ounce of food you put in your body should be as high quality as possible, by quality I mean it should have a lot of protein and not a ton of fat or excessive ammount of carbohydrates.
2. Take your vitamins! I take a multi-pack, as well as extra B's, C, Zinc and Magnesium. If you're short on cash or don't feel like taking pills all the time, a solid multi-pack will be fine. Most single pill multivitamins are subpar in my opinion though.
3. One of the only supplements I've found to be useful is Glutamine. It's not some super supplement (nothing legal in the US is) but it will indeed help one keep quality mass on while consuming fewer calories. If you use it for what it can do (help prevent catabolism from what I understand) it can be great. Just take a few capsules when you should eat, but can't, won't or don't. It's worked for me over the past few months at least. To a lesser extent I also found BCAA's to be useful in terms of maintaining muscle mass while losing fat.
4. It is indeed possible to lose fat and get stronger as long as you train smart, eat at least semi-smart. Just like anything with lifting, it often becomes a confidence issue. Lifters can get it in their head that if they're not stuffing food in constantly, they can't perform in the gym. Now obviously, I am a proponent of a high calorie diet for most lifters, but that doesn't mean you can't continue to progress while limiting your food intake. I lost weight while making amazing progress on my bench just recently. Don't sell yourself short.
I hope that's of some help.