Many of the descriptions above assume that (1) there is only one time travel paradigm in science fiction, (2) it can be described using the current physical model of the universe, and (3) the current physical model of the universe is correct. These are huge assumptions.
"Back To The Future". Things that are altered by the time traveller fade away rather than vanishing instantly. Those who haven't experienced temporal shift do not realize anything has happened. Those who do have full memories of the universe as it was before things changed. Why is this?
Well, what does the flux capacitor do? "It makes time travel possible." How? In what way? These things are never explained, but I would guess that a thorough explanation of the inner workings of the device would shed some light on the subject. Perhaps a temporal wake is created by chronometric particles, a la "Star Trek: First Contact". Perhaps changes to the timeline do not propagate instantly, but rather ripple down the timestream. In some cases they cause physical damage ("Millennium"'s time quakes). In Marty and Doc's world, obviously not.
"Bill & Ted's Excellent Adventure" presents a different paradigm. Events of the past are NOT changed in this film. There is no dramatic altering of events in the film, no paradoxical destruction of cause-and-effect dynamics. To Bill & Ted, Lincoln, Socrates, and Joan Of Arc exist in the past. To Rufus, Bill & Ted exist in the past. To another observer, Rufus appears in the past. What does this mean?
It means that to an outside observer, all events are happening simultaneously. Think of the actual film stock that the movie is printed on. Each frame, from start to finish, already exists and can't be altered. Bill & Ted come to understand that, and as a result can spontaneously generate things out of thin air. They are committed later to go back and supply everything they've conjured, and indeed they must. They can't decide later that they don't want to. All events are predestined in this universe, but no one inside the universe can be sure of this. Only the outside observer can see what laws rule over Bill & Ted.
In "Time Tunnel", the protagonists jumped around through time, arriving for key moments in history, such as the assassination of Abraham Lincoln or the bombing of Pearl Harbor. No matter what they did to try to alter the course of history, they failed. Did the laws of the universe prevent them from changing history, or were they just really bad at it? One would assume the latter, or folks would rapidly lose interest in the show. But it's the author who determines the physical laws of the universe they're creating.
The "12 Monkeys" world precludes changes from being made -- Cole is sent back in an information gathering capacity. In desperation the board from the future decides to change the past. Cole fails to change things, instead fulfilling the predestined time cycle as a frightened young Cole looks on in the airport terminal.
The real key is to either obey your own rules, or have a damned good reason for breaking them when you don't. If you don't have a good explanation for how things work, just toss out a McGuffin. Fiction is all about the suspension of belief anyway...