The Allied States Marine Corps only appears in episode 22 of Season 1. At the time of their appearance, the Allied States of America was still known internally as the United States of America, while President Tomarchio and the rest of the Cheyenne Government (possibly Congress) debated on the name changing, thus, in the episode, Colonel Hoffman refers to them as the United State Marines. Note that all of the Marines at the base have the new vertical-striped flag of the Allied States of America on their uniforms.
At the end of episode 22, Colonel Hoffman attends a video conference with his superiors. They instruct him that he (and his Marines) should re-prioritize, and head to Jericho, Kansas, to hunt for a known terrorist. However, in the first episode of the next season, the Allied States Army appears to have been sent to Jericho, and not the Marines. It is speculated that either the Army was later chosen, as they have more manpower, or if the show's budget cuts may have hindered them from using the Marines again. Also the actor who played Hoffman was not available.
Colonel Robert Hoffman - Commander of the Marines in Nebraska