As an absolute beginner, I highly recommend reading Mark Rippetoe's Starting Strength book. It outlines 5 basic lifts that will exercise just about every muscle in your body. Those exercises will make you very strong. The book itself breaks down the lift step by step, and also provides some troubleshooting to help you get it right. I've written an intro to strength training a couple months ago that will at least help you decide what you want to do.
Essentially as a beginner, your are at an ideal position.
- You will be able to gain strength every time you work out for the next few months
- You will be able to burn fat and get strong at the same time (assuming you are careful with what you eat)
Of course as a beginner you also have some challenges:
- You may not know how to do the exercises
- You will have to be OK with not having a large number of plates on the bar (most people I see in the gym don't)
- You may not be able to discern when advice someone is giving applies to you and your goals or not.
- You don't know the importance of recovery yet (what you do outside the gym)
Check out the "Intro" I wrote, which will help you decide how to get started. The first step is finding a program that works with your goals. Since you are brand new, following someone else's beginner program is going to be more beneficial than randomly picking up weights and doing stuff. The beginners programs will usually have the big three: squats, bench press, and deadlifts. Also very common is the overhead press. A little more devided would be the opinions on whether beginners should start with power cleans (a very good, but very technical lift) or simply do barbell rows.
The basics of nutrition for a weightlifter is this: 1g protein per pound body weight, and the rest of the Calories as you see fit. Your muscles don't know or care whether the energy from the food comes from carbs or fat. Some things are clear, such as if you eat more Calories than you burn regularly you will gain weight. Some things are less clear, such as what impact carbs has on your body, and when you should have them. In some ways the more active you become, the less critical it becomes.