Swivel,

I'm not sure which agency you've applied to and the specifics of the FIT test.

Still, no matter what the test is, one thing is definite: it will involve some sort of middle distance run.  If you don't run on a regular basis, you need to start running NOW.

First, pick up a good set of shoes. You need to visit a specialty running shop in your area with a knowledgeable staff that will help you find the right shoes for YOUR body mechanics. 

Case in point: A few years ago, I had a pair of great Asics running shoes that reached the end of their useful life. Unsure of the model name, I went into a store and picked up the most expensive Asics running shoe, the Gel Kayano. To my dismay, I hated them—it was like running in cement loafers.

I later found out I bought a completely different style of shoe from my last pair. The Kayano is a motion control shoe, designed to help people who pronate severely (feet roll inwards). It was way too much for me, as I am nearly neutral, and also wear custom orthotics (shoe inserts—I get them on the cheap, as a friend is a nationally renowned pedorthist).

I then went out and bought the newest model of the shoe I originally had (found the box with the name), the Gel Nimbus-a cushioned shoe. What a difference. They are super plush, like running on pillows. 

Once you get shoes, you can think about a program.

I would run distance (20-60 minutes) 2-3 times a week, sprint/interval workouts 1-2 times a week.

Taku's Interval Training is a great workout favored by many athletes involved in the sport of mixed martial arts (more commonly known as “Ultimate Fighting”). Keep it down to 1-2x week, because it will kick you in the ass if you do it right.

Another workout you may wish to consider is something by Stew Smith. He has a fantastic reputation, although I cannot personally vouch for any of his materials. I just know that a lot of people swear by them.

Lastly, you may wish to consider a heart rate monitor. It can really help guide your training and let you know when you are doing too much. Polar makes a great product—check eBay for some good deals.