If you want to emphasize that two (or more) people will be in the same state, and maybe it's unexpected that this is the case, "the very same state" conveys that. E.g. "Mary and John each separately booked a vacation to Florida. Coincidentally, they will be in the very same state."
If you want to emphasize that some people will be in a particular state, maybe where something else interesting is going on, but it's less interesting that the different people will be in the same place, then "the very state" can be used. E.g. "Mary and John will be in the very state that sent the first people to the moon."
"the same very state" doesn't sound right. "very" in this context means "particular" or "exact" - for some reason it's ok to say "the same exact state" but it's unusual to say "the same very state." Not sure if there's any good reason for this.