In EU2, natives represent aboriginal peoples in a province. Most unowned provinces have natives when the game starts, although a few remote islands are completely uninhabited. Natives make colonization and exploration more difficult, but they can give a nice population boost to colonial cities.
Natives can be in one of two modes: either inactive, or (having been provoked), as an army. Inactive natives are represented on both the main map, and on the province display, as huts. When natives have risen up, they show as an army on the main map, but huts are not shown.
Native Attributes and Growth
Native populations in each province are modelled by three numbers: number of natives, max number, and ferocity. When they are inactive, you can see their number and ferocity by mousing over them on the map or on the province display, and reading the tooltip. Their max number is available in province.csv, and can be inferred in-game easily. When natives have risen, you cannot see anything about them other than their number.
When natives are at less than their max number (due to disease or combat deaths), they grow extremely rapidly until they reach that number. The growth ranges from 100 population per month, up to 500.
Effects of Natives
Natives make colonization more difficult. If they are present in a province they reduce colonization chances a variable amount depending on their ferocity. (There is a useful exception here: when they have risen up to attack, they exist on the map as an army, and are not counted as being in the province for colonization purposes.) Also, they occasionally rise up during colonization and take over or even destroy the colony. (A garrison can prevent such ill effects, assuming it wins the battle.) Native uprising may happen each time a colonization attempt fails, but it also rarely happens for no reason at all. Both effects seem to happen based on ferocity. On the plus side, natives may be incorporated into a colony when it becomes a city, thus getting a nice early population boost.
Natives also make exploration a bit harder, since they may rise up whenever an army enters their province via land. (Entering via a port is safe, and thus preferred if possible.) The chance of this happening is related to their ferocity: with 0 ferocity it almost never happens; with ferocity of 9 it is automatic or nearly so. Conquistadors clearly make uprisings much less likely; I've seen them entering more than one province with ferocity 9 natives without a fight.
Natives always have land tech 0 for combat; thus, once you get to land tech 9 they won't hurt you much in combat unless there are huge numbers of them. However, if there are enough of them, and the offending army is very small, they may be able to kill it. Humans can start a battle with natives automatically if they have an army present in their province, simply by clicking the "attack natives" button. You can use this feature to intentionally wipe out natives, to clear provinces for colonization.
If combat kills enough natives, they'll be eliminated permanently in that province. Once killed, they cannot return. If they are not wiped out, they'll usually take casualties, which will reduce their number. When they are reduced, they'll recover very rapidly (at rates of 100/month or more), until they return to their max number. Note that when you complete a colony with natives present, whatever number they currently have will be the amount of population incorporated. Thus, if you're colonizing a place but had to beat down the natives just before you are going to finish, sometimes it can be good idea to wait just a few months to let the natives recover to their maximum before sending the last settler.
In the New World, the first time any army enters an unowned province, 3/4 of the natives will be instantly killed. (This is a done according to a "whiteman" boolean variable that the province has.) This is a one-time effect only, but it can be very useful to help you kill off aggressive natives.
Here's the rules of thumb I use for whether to kill natives or keep them. In early game, I'll try to incorporate all natives up to aggression level 3. With aggression at 0 or 1, I don't bother to garrison unless it is convenient. At land tech 9, I'll also try to keep the 4s. Once I get to land 14, I try to keep all natives up to aggression 6, if they are numerous (3000+). It's not worthwhile keeping small numbers (<3000) of natives if they are more aggressive than 4. In all cases, if I'm trying to incorporate natives I start by attacking the natives to get them to rise, then running away, to get the best initial colonization chances.