Time and Relative Dimensions In Space

Kryten: All the ship's chronometers indicate that this is August the 16th, in the year 1421, just one day out.
Rimmer: Give us visual. Let's see what it's like out there.
Lister: Okay, punching it up. ... We're still where we were!
Kryten: Of course. We're still in deep space, sir, only now we're in deep space in the 15th century. Isn't it wonderful?

—Red Dwarf, "Out of Time"

When you go back in time, where do you end up? There are several options:

You remain at exactly the same geographic location

Basically, you don't go anywhere. More accurately, you arrive on Earth at precisely the same longitude and latitude you left from. This ignores the motion of the planet and its tectonic plates, but the nature of relativity means that there's nothing "incorrect" about not ending up in space or the middle of an ocean.

H. G. Wells' The Time Machine. The traveller can see the world outside the windows rushing past in a blur, so the time machine is physically remaining in place and just being sped up somehow, not "teleporting" through time (so, like any object resting on the ground, it's carried along with the continental drift). The original text explicitly explains that the forward-moving object exists in a state rarefied by the factor of its time speedup, so to non-travelling observers it is virtually invisible, and collisions are no problem.
The Back to The Future films (but not the animated series, see below).
Time travel in Achron.
The film Harry Potter and the Prisoner of Azkaban (but not the book).
The The Girl From Tomorrow series.
The Mirror Mirror series (the Time Portal is only active when both parts are "aligned").
How Gates originally work in Chrono Trigger.
- Justified in that the Gates are basically bidirectional wormholes anchored to specific points in space and time at either end.
- The Epoch does this too until it gets upgraded whereupon it goes all the way around the world in order to end up right back where it was (spatially) every time it travels through time.
Stargate SG-1 had conflicting takes on this. In the very first instance when time travel appears in the series ("1969"), SG-1 enters the Stargate and is transported to the 1969 version of Cheyenne Mountain, with the Stargate immediately disappearing behind them. However, in subsequent instances, including the end of "1969" and the end of "2010", objects traveling through time via the Stargate are transported to wherever the Stargate is located in that time period. The RPG later explained the initial discrepancy by saying that SG-1 was transported to the same geographical location because both of Earth's Stargates were inaccessible at that time.
Red Dwarf, as noted above. It is very boring to note that, the only other time they use the device, it takes them back to Earth for no explained reason.
- Rule of Funny. You can hardly turn Lee Harvey Oswald into a street pizza if you're 3 million years from Earth.
The few times time travel happens in Darkwing Duck, the travellers stay at the same location. Awkward when the location becomes a no-parking zone in the future... or is in a bridge tower, and you go back before when said bridge was built.
Played as well as can be expected by William Sleator's Strange Attractors. The villains have a base in the ice age, and since the earth was a great deal lower back then, they have actually built a ramp in that age so that they can jump from a specific location in the present and simply drive down it to land level.
Mahou Sensei Negima does this, although the device is magically powered, so A Wizard Did It.
- Although it's averted if the time jump is long enough; it's a little less accurate then. For instance, when they go back a full week, they end up in the same general area, but hundreds of feet in the air.
The consequences of a very similar idea are discussed in Sluggy Freelance in the story "A Very Big Bang", though it doesn't involve time travel as such. The protagonists of the story have entered an alternative reality and are trying to escape it by using a remote controller they have to reopen the portal through which they came, which will open at the same location it originally did. After the planet in question is blown up, Riff, the inventor of the device, says that the portal will open at the point in space where that point on the planet's surface would have been if the planet still existed, accounting for all the motion in space it would have made in the meantime. Why? Well, if it were to remain at the same geographical location, that's how it would have to behave. No explanation is actually given.
Used in Life On Mars and both pilots for the American remake, with Sam waking up in 1973 at the spot he was hit in 2006. This was somewhat averted in the first episode of Spin-Off Ashes to Ashes, with Alex getting shot in a tunnel near the warf and waking up on a yacht. She stays in the same vicinity, but not exactly at the same place.
Pretty much every instance in Star Trek. TNG's finale involved a Negative Space Wedgie formed because they were applying phlebotinum in the same way to the same "spot" in three different time periods--non-related time periods, at that.

You end up in outer space

Why? Well, the Earth is moving around the Sun and it pulled away from you when you traveled through time. Pretty clever, but it runs into a few issues with special relativity (see here. When you think about it, it's not clear just what the traveler is staying "still" relative to).

Occurred in Deadlands.
Same Time Next Year by Neal Shusterman.
In the Stargate Atlantis episode "Before I Sleep", Weir, Sheppard and Zelenka activate a time-traveling spaceship located in the Atlantis jumper bay. After going ten thousand years to the past, they emerge in outer space around Lantea. (This contradicts the episode "Moebius" of Stargate SG-1 in which another time-traveling puddle-jumper follows the above rules, although it could just be argued that the SG-1 time jumper was a later model in which this "flaw" was corrected.)
In the British comic Strontium Dog, this is actually used as a weapon, with time-travel guns, bombs and mines.
In Joe Haldeman's novel The Accidental Time Traveler, each use of the time machine also moves you a progressively longer distance (which can be precalculated if you know the formula). The first few times it's used the distance moved is millimeters or less, so no one realizes, but eventually each use involves teleporting to the other side of the continent and then leaving the planet altogether.
The protagonists in the German movie Das Jesus-Video were shown a recording of a time travel experiment in which an apple was moved a few seconds into the future and reappeared next to the time pod,
In the micro-fiction story "The Time Traveller".
In Spider Robinson's Callahan's Con, a distraught Zoey travels into the future to make sure her daughter is all right, but forgets to take her geographical location into account and accidentally ends up off-Earth. Fortunately her husband Jake, their super-genius daughter Erin and the rest of the Callahans regulars are able to bring her back safely.
An early example is Clark Ashton Smith's tale The Letter from Mohaun Los wherein the protagonist suffers this fate unexpectedly but continues to keep time traveling believing eventually he will juxtapose with habitable planets, which he does.
In the Piers Anthony novel Ghosts this is taken into account, and the time-ship the cast use to travel into the far, far future is affixed to a point of absolute rest while the rest of the universe continues to move around them.

You end up somewhere else for no explained reason

The real reason is almost always to serve the plot, of course. If you were in California and you went back to the year 1066, you wouldn't want to end up in the pre-Columbian wilderness, would you? Sure, there would be Native Americans around, but if you went to 1066 you would be hoping to check out the Battle of Hastings in The Middle Ages, right? This can also occur on a smaller scale, e.g. you end up on the other side of town for no reason.

The book version of Harry Potter and the Prisoner of Azkaban where Harry and Hermione are transported from the infirmary to the entrance hall when they go back three hours. Fans tend to Hand Wave this by saying that the Time-Turner takes you to more-or-less where you were at that time. This would suck, since the Harry Potter universe observes the Never the Selves Shall Meet rule.
- The film has them remain in the infirmary as they travel back.
Journeyman, although Dan almost always remains within San Francisco.
Seven Days is somewhere between this, the previous and next scenarios; the sphere seems to always materialize in space, then falls back to Earth, landing at a more-or-less random location, usually in the general vicinity of wherever Parker was aiming for. The most we are told is that the spacial component of the guidance system is far less accurate than the temporal part.
Scott Ciencin's Dinoverse novels have the characters sent back in time but landing elsewhere on the planet, and one of them even comments how lucky they are not to be in space.
The Time Traveler's Wife. Of course, for Henry DeTamble the whole process was involuntary and random. However, when he travels back to his present, he will usually go back to the same spot where he came from.
- Which is why he avoided flying on planes.
On Lost, moving the island lands Ben ten months into the future... and in Tunisia. This may be related to the fact that Tunisia is on exactly the opposite side of the earth from the island.
- However, when a person travels in time alone, they travel into their past self and don't technically move at all.
In the film Time After Time, H.G. Wells and Jack the Ripper both end up in San Francisco. This is given a bit of a flimsy Hand Wave with Wells observing that it's eight hours later (which one guesses is supposed to suggest that the planet has rotated on its axis, but fails to explain why the time machine ended up on Earth at all with all the other planetary movement).
- Since Wells arrived in a museum where the machine was already on display, it can be presume it just brought them to itself.
In Sluggy Freelance, when Riff's time machine malfunctions, it sends Zoë and Torg from the United States to medieval Britain. This is apparently because they're following the time-space-trail of the demon K'Z'K, but that doesn't explain anything since K'Z'K was blasted there randomly too.
Occured in the book Kindred by Octavia Butler. When the main character travels back in time, she always lands somewhere near the boy who [presumably] called her there (he seems to do it unconsciously whenever in deadly danger), i.e. Maryland, and when she returns she always lands near where she started, that is, her home in Los Angeles. On her last return trip, however, she materializes with one arm literally in her home's wall.
Pretty much the entirety of The Time Tunnel depended on this concept, otherwise our two intrepid American scientists would have spent a lot of time underground.
Futurama "The Late Phillip J. Fry", The time machine, having gone from the present to the future to the end of the world, then to the past so that they can arrive at the present again. When they finally arrive, they are ten feet above where they started, gravity kicks in and they end up crushing themselves before they ever left in the time machine.
- In reality, they don't travel to the past, they instead keep going forward until a new universe is created, then another, which is identical to the first except "10 feet lower." The machine otherwise follows the first option.
In the episode "It's About Time" of My Little Pony Friendship Is Magic, Twilight casts a spell that lets her go back seven days for a limited time, and also transports her from Canterlot to her house in Ponyville for the duration of the spell.

You get to program your destination

Basically, a justified version of the above (and possibly a way of dealing with the above). Very common. Essentially, this means that your Time Machine is not only capable of time travel, but also teleportation—it just engages both at the same time. Think about it—if you input a destination, but keep the time the same, you can instantly travel anywhere! In a sense, this may be the most scientifically accurate scenario, since according to Einstein's special theory of relativity, teleportation and time travel are actually equivalent. It is not possible to travel instantaneously from one location to another without appearing to some observers to have traveled backward in time.

Mr. Peabody's WABAC machine in Rocky and Bullwinkle
The Trope Namer itself, the TARDIS in Doctor Who. Its ability to travel in space is treated as being nearly as important as its time travel.
- Because of this it can jump across the entire Universe in an instant. In "Pyramids of Mars", the energy beam from Mars that is powering Sutekh's prison on Earth is shut down, but the TARDIS can get back to Earth in time to lay an ambush for Sutekh as the energy beam was moving at light speed, giving them several minutes before the prison will fail.
- A rare example of the second type occurs in one Expanded Universe novel. The Doctor sets the TARDIS to land in Masada, but a glitch causes them to land in England. However, the TARDIS is still calibrated to compensate for the Earth's spin at the latitude of Israel, not England, resulting in the out-of-control TARDIS carving a police box-shaped tunnel across the English countryside...
- Another minor example of the previous type occurs in Fear Her, when the Doctor lands the TARDIS with the door against a dumpster, and must then turn the TARDIS around before he can leave, though that example might be more of a botched parking job than anything else.
- The Tabletop RPG includes a section explaining how the TARDIS systems can be used to compensate for the rotation of planets. The most common error in travel is appearing in the wrong place.
Back to The Future The Animated Series
The Number of the Beast by Robert A. Heinlein had their device able to travel along any of the six dimensional axes; thus, it could travel through time, space, and alternate dimensions.
Where in Time is Carmen Sandiego?
The Time Scooters (one- or two-person) and Time Transports used by members of the Time Patrol in Poul Anderson's series of short stories and novellas.
The tabletop RPG C°ntinuum, where time travellers can also move to arbitrary locations on Earth, but travelling requires extensive augmentation and training as the Earth's constant movement through space makes aiming really hard.
In Meet the Robinsons, the time machine—for the most part—arrives in approximately the same airspace in which it left, except for the trip from the Robinson Manse (circa 2037) to the 6th Street Orphanage (circa 1995), meaning the time machine probably travels through space as well.
Hiro from Heroes has abilities that seem to count time and space as part of a single continuum. His first attempt at actual travel through space landed him several weeks in the future as well.
Chronos, the Incarnation of Time from the Incarnations of Immortality series, uses an hourglass to time travel. It usually does this automatically, but he can negate certain parts of it, allowing him to do such things as stay in place while the universe continues on its merry way.
The phone booth in Bill and Teds Excellent Adventure works like this, allowing the user to dial a single phone number for both location and time.
The Legion of Super-Heroes' Time-Bubbles.
Speaking of Einstein, Red Alert's Chronosphere works this way, warping from an unknown location to a square near where Hitler was. Cherenkov uses a similar system in Red Alert 3 to delete Einstein from history, warping from the Kremlin to an auditorium where Einstein was just leaving the stage.
In Haruhi Suzumiya, the use of the TPDD (Time Plane Destruction Device) apparently works like that. In Vanishing a time traveler is explicitly given destination time and place coordinates before using it.
In the Dragonriders of Pern series, dragons have the natural ability to teleport anywhere they (or their rider) can visualize (they can also go places they haven't seen, but they run the risk of appearing inside a mountain or being lost forever). A lesser known side-effect of this is that they can also travel to any when they can visualize. They can also do both at the same time.

You end up nowhere at all

You end up in a different dimension, or otherwise not in the known universe. Usually this means there was some sort of problem.

In Isaac Asimov's short story "Blank!" the machine gets stuck "between two time-particles".
In Chrono Trigger, if you try to travel through time with too large a group at once, you end up at The End of Time. After having wound up here once, this becomes the default result of going through a Gate.
In the SpongeBob SquarePants episode "SB-129", after visiting the future and the past, Squidward ends up...somewhere big and empty, where he can finally be alone. A few seconds later, he desperately wants out.
In Sluggy Freelance, most temporal accidents put you in "timeless space", which is mostly full of geeks who made their time machines malfunction on purpose to see what would happen.
In Stephen King 's The Langoliers, travelers through a time rift end up in a "used-up" version of the past—all the people are gone, everything is worn out and useless, and monstrous things are coming to devour what's left.
- And King's short story The Jaunt (in Skeleton Crew) explores an opposite effect - instantaneous travel through space is not instantaneous travel through time... it's longer than you think.
In Larry Niven's Temporal Research Institute stories, Hanville Svetz is sent to explore the remarkably extraordinary past, where he and his superiors marvel at the many strange things they see in each period—never realizing that they aren't sending him into THE past, but merely A past (generally cribbed from other fiction and mythology). At least he's better off than most: Since there's an infinite number of parallel timelines, it's pretty much impossible to find any particular one twice, but Svetz doesn't know this, because his time machine is a stationary device on the end of a column that's extended through the fourth dimension during each expedition, preventing him from getting marooned like many others.
In The Redemption of Althalus, the heroes live in a house that can open doors to any place they want and, it's hinted, any time. One of the heroes decides, as an intellectual exercise, to open a door to "Nowhere", and nearly dooms everyone. He receives a severe tonguelashing by their local goddess, who remarks that not even gods would try something like that. He then says his next experiment was to open a door to "Nowhen"...
In the Marvel Universe, the time-traveling villain Immortus makes his headquarters in Limbo, a realm "outside of time" from which all time periods are accessible.