If a soldier has one foot planted on US soil, then Habeus Corpus does in fact apply.
If a human being has both feet planted on US soil, the military have no right to detain them or do anything besides make polite suggestions, regardless of any suspicions about the person's nationality, probable cause or any of that.
This is one of the most fundamental constitutional issues in the US. I'd think about it a lot less lightly if you're going to claim to support things like "liberty" and "rights".
You'd think that, wouldn't you? But you'd be wrong. Don't feel bad - I was pretty surprised as I learned more about the subject too (IANAL but am planning on a law career, and already having an interest in this I figured I might as well learn it properly). The law and administration of immigration have been patched and reorganized so many times that the subject is an elective on most law school courses.
Unlike most other branches of law, the scope and administration of which are constitutionally limited, immigration is plenary law - an area in which the government has absolute power and its actions are not subject to judicial review unless otherwise stated (going back to the Supreme court's decision in the Chinese Exclusion Case in 1889, holding that where aliens are concerned, only property rights are constitutionally protected and others may be revoked as the government sees fit). So the ability of the courts to entertain petitions for Habeas Corpus in immigration cases is quite limited (and defined by statute), and other kinds of legal action (eg certification of class action suits) are off-limits altogether.
In cases where the jurisdiction of federal courts is at issue, the government often argues that the terms of a visa or similar document an agreement or bargain (but not a contract) between the US and the alien, formed outside the US for legal purposes. It is thus asserted to be a private matter between the government and the individual, outside the scope of judicial review. The Attorney General or the Director of Homeland Security has more or less absolute discretion in such cases.
This leads to some odd outcomes. For example, if someone sneaks across the border and is later arrested and tried, they have full constitutional rights. If at any point they are handed over to DHS, they have the right to a hearing in front of an immigration judge (part of the DoJ) to determine their legal status, and can appeal any decisions to either a special immigration appeals court in DC and/or the federal courts (depending on exactly what the situation is). The same is approximately true of someone who overstays or commits a crime violating the terms of their visa. On the other hand, some 30 million people visit the US every year without a visa as tourists. If a DHS officer determines such a person has violated their conditions of entry they can be arrested and deported or detained pretty much at will, with no opportunity for a hearing at all (unless they claim asylum, which of course happens all the time as a result). The government's current view is that such persons have no constitutionally protected liberty interest, putting them outside Habeas Corpus altogether.