Well, there's a couple things you may be missing that make this perfectly realistic.
First of all, the analogies between Golarion and Earth are intended to be rough. The Shoanti are kinda Native American-ey - but they're also Celtic-ey, etc. The Linnorm Kings (Vikings) are located immediately north of Varisia, so you can draw as much Gaul/Celt analogy with the Shoanti as you can Native American, and it also provides a hint that it's probably not all that hot out.
Secondly - we have Native Americans that far north in the real world, you know. In fact, the Blackfoot, Cree, Crow, and Sioux are from right around that latitude.
Thirdly - "Deserts" can be found at any latitude. A lack of water isn't correlated with "hot." The Storval Plateau is more like the Russian steppes - not hot, but dry. The Cinderlands are hot because of volcanic activity (and the resulting brushfires), not climate. There's more on the Plateau in Rise of the Runelords and the Kaer Maga sourcebook which can provide you with better local color. For real-world analogues, try out the Ryn Desert in Russia/Kazakhstan - in fact, the Kazakhs had native steppe horsemen you might well tap for inspiration. Just reading that Wikipedia article you start to see some direct analogues to the Shoanti (oh look, eagle hunters...)
Fourth - yeah, game writers aren't always super precise. The continents are a little bit more north than you'd think; the "equatorial heat" of the Mwangi Expanse doesn't come anywhere near the Equator. And art direction is always a challenge, so you get some depictions of Shoanti wearing a bit less clothing than they probably should be for their locale. Not a new problem - compare this photo of actual Crow to this painting of a Crow by some white guy. From the time of the Greeks, everyone knows art's better when the subjects are nakeder. C'est la vie.
I love using gaming to drive me to read some real history... Instead of sticking with the Hollywood "Indian/desert" image, check out Caesar's Gallic Wars, the Kazakhs, some tales of Dakotas-area Native Americans, etc. and mash it on up.