I think when T-45Heinous mentioned not wanting to work for a regional (because of loyalty), it is a more polite/upbeat/tactful way of saying: the pay is insulting, and there are better opportunities. If he has the experience, and all he has to do is maintain 100 hours of currency/year, and flight instructing in a 172 pays more than flying for a regional, it is a no-brainer. Also, he mentioned he is currently on active duty staff tour, making it intuitive he is looking for a weekend job where someone else is footing the bill for his currency.
Here are some steps for finding a job:
1. Pilot Jobs, Aviation Jobs, Aviation Employment, Job Fairs, Career Fairs
2. Use the search function on this site, there are some other job boards out there, and people on this website have already written reviews on them.
3. Yes, probably Googling the local flight schools, where you might want to work, and giving them a phone call.
4. After you get going, you might meet some of these doctors and lawyers, skip the flight school, and teach them in their own plane