At the time the Mormons arrived (1847), it was officially Mexican territory. But the US annexed it in 1848. By the time of the Utah War, it was US territory.

(BTW, the canyon by which they entered the Salt Lake Valley is Emigration Canyon. Emigration is when you leave, immigration is when you arrive. They were consciously leaving the US. They weren't really "going to Mexico", though; they were intending to form their own independent country. But a year later, the US annexed the area.)