But, I think if there were such forces, wouldn't they be more properly called the United Federation Marine Corps (UFMC)? Calling them the Starfleet Marines would be like calling the current day USMC the Navy Marine Corps.
I just think that the phrase 'Starfleet Marine Corps' sounds better, that's all. It may not be applicable in today's military but within the context of Starfleet, I think the phrase sounds better. And it would fit with Kirk's comment that Starfleet is a combined service.
As for uniforms, my supposition is that the SFMC of the TOS era wears a black uniform. Same design we're familiar with, just in black. Don't you think that would look cool?