Native terrain is a creature's "home" terrain type. It gives creatures fighting in their native terrain +1 attack, +1 defense and +1 speed. Additionally, a hero moving on a terrain that causes movement penalty with only creatures native to that terrain will not suffer movement penalty. Heroes with any creatures native to another terrain will suffer movement penalty. Nomad's sandwalking is the special ability with its own mechanics, not the regular native terrain feature. Creatures on native terrain are able to detect Quicksand and Land Mines. Neutral creatures do not have a native terrain.
Sieges are always fought on town's native terrain (e.g. Inferno town sieges are fought on lava).
Cove's Grail building Lodestar makes every terrain native to friendly Cove creatures, permanently granting them native terrain benefits.