I used to work in one of those running shops with the treadmills and gait analysis.
Your gait will evolve as you run, some people have pronation that you can only see at a proper run, not a jog or walk. Don't get fitted for shoes until you actually have a running style. If you have seen that you get a inside/outside wear pattern on your walking shoes in addition to having previous knee problems you may need to do something different.
I'm seconding starting with cheapish shoes, BUT, they should be a neutral shoe (not meant to correct over or under pronation), and an old model of running shoe rather than the 'fashion trainers' sold by Sports Direct etc. If you run in the wrong corrective shoe you can cause damage to your knees.
If you have thin feet, the Asics Cumulus or Nimbus are a decent choice, if you have wider feet, New Balance can be really good (780, 910, 880 are all neutral).
To see if a shoe is neutral, turn it upside down, if the sole is broadly symmetrical (you are testing for the density of the material, but most manufacturers make the denser corrective material a different colour). If the shoe has holes through the bit under the ball of your foot, try to look straight through it - you can look through a neutral shoe but not a corrective shoe.
After running for a while, you'll get used to the difference between being sore from muscles and being sore from joints. Listen to the joint pain and stop. Also, if you've rested a joint for a while, it feels fine walking and then you run and it is sore within a few minutes, it is time to see a physio.