The best answer for you really depends on what your overall goals are, whether you are attempting to be in shape for any type of sport, etc. As a result, the advice in this answer is more generic.
The basic approach for "doing it right" is:
- Decide on your goals
- Develop a plan
- Execute it
- Check your results against your goals
You mentioned "gaining strength", and one of the primary ways of doing that is lifting weights. Along with that activity is gaining muscle. "Shape" is a little more nebulous, and depending on who it's coming from can either refer to conditioning or aesthetics. I'm assuming you mean conditioning.
Now, if lifting weights appeals to you, there are a couple great resources out there for beginners. I recommend reading this "Intro to Strength Training" to help you get started. It will refer to a couple beginner programs for strength training, and provide some generic information to help you decide between them. The programs are your first plan.
As to goals, you want to choose goals that are easily measured:
- 5 more pounds on the bar than last time
- I want to bench press my body weight
- I want to be able to do 12 pullups at one time
The important part of the goal is that you know when you've achieved it, and it's something you honestly believe you can do. Don't set out to deadlift 600 lbs right off the bat. Start with a more modest goal that's above what you can do now. When you get that goal, increase it and push for more.
Keep a log of what you did, and how you felt, or if you think you didn't do something quite right. Review the log with your trainer, or just review it yourself. It will help you figure out why you might not be hitting the goals you've set for yourself, or let you know when you are really close. Once you've filled up the log book, start a new one. The old log book will only be important for a little bit. You can use pen and paper, or an app on your smart phone, but just keep track.
Eventually, you will have to change your plan/program. Those changes are required either because of your advancement as an athlete, or because of changes in your more immediate goals. If you start out with an interest in soccer, but then develop a love for cricket, the style of training will need to be adapted for your new sport of choice.