You should always focus on improving the technique instead of strength - you will gain strength automatically while you are climbing. To climb better just climb.
The same goes with overhangs, the more you climb the better you'll get. Of course its inevitable to think of gyms as a source of strength training but bouldering should suffice to help you get stronger.
Running will allow you to gain more stamina, but long routes can do the job too :)
Start with the easiest grades and move to harder grades, when you find that you are feeling a specific grade easy. I can suggest a good blog which is written by a good old climber named Stevie Heston. Learn from more experienced climbers to gain good footwork as it is far more important than strength.
When you start to lead, you will enjoy climbing at a new level.