Hi Conair,
I dunno about schools in the VA area. I've been mostly based in FL although done some time up near Boston and LA. Just take a look around when you are here.
As to how you do it, is up to you. I started 11 years ago with a large pt141 school in MO. It went bust quite quick and I finished up with a company called Airgo in IL which was a small pt61 "pay as you go" type of deal. Pt61 is more flexible and pt141 is more structured. Airlines seem to hire both although some might prefer ex-pt141 people.
It almost doesn't matter as to how you do all you ratings, more the number of total hours and particulary the multi time. Many go and do the instruction route (myself included) to build the time. You should aim for the IFR pt135 mins (1200TT) with about 100 hrs multi time.
Given the bouyant pilot market here right now, you will easily qualify for most regional airlines and cargo operators with that kind of time. Regionals run about $17,000 in the first year. Pay For Training is all but dead with most operators. One or two still exist..avoid them!
Instructors are in heavy demand so it should be easy to get a good position almost anywhere. Pay is not good however, but is supposed to be improving, typically $10-15ph maybe more with a larger school like Embry Riddle.
Hope that helps. Good luck with the immigration paperwork. Are you applying for a K1 visa?