http://www.foia.gov/how-to.html
This link gives information on how to submit a foia. I submitted mine through the regular mail.

Regarding the scenario you describe, I would start with the state from where the soldier served, but that is just my opinion. Good luck!