Good luck with this! I did the couch to 5k program about two years ago, and I think it's really great. All the other "beginner" running programs I looked at assumed you had a moderate level of fitness already, which is unrealistic for someone like me who couldn't even run for a minute straight before hand!
Like leedswest said, the best way to lose weight is doing cardio, but if you want to maintain muscle in order to get the toned look, you need to use weights as well. You could try out some of the machines at your gym, though freeweights (dumbbells) are the best as the exercises done with these engage the most muscles.