Well... first you actually need to have ancient history to call on. If you don't, it'll be hard to just simulate. That's what made LotR work in this way; Tolkien had all that history at his fingertips and could refer to it casually in passing. Pulsehead's answer provides one way to accomplish this. Assuming you've done that work already...
Physically layer the settings
What is now is built on what came before. Show this physically and literally: a new town built on the ruins of a fallen city, a forest flooded and slowly becoming a swamp, a city with concentric rings of massive stone walls deep inside it, showing the boundaries of the town as it expanded out of its walls over and over again.
If you can tie these to important events, all the better: Why is the city ruined? What made the forest flood? Why does the city need walls, or what makes it so prosperous?
Name things for people and events that have come before
You can't throw a rock in certain parts of Britain without finding vaguely flat-ish rock formations called "King Arthur's Table," and the number of "Indian's Head" locations in America is astonishing. A good number of American States have names derived from the Native Americans who called that place home. Groups of people will have the family names of their conquerers for generations after the conquerers went home or were in turn conquered. Don't forget the natural tendency to name things for our heroes, victories, and sponsors: Washington DC, Trafalgar Square, Jamestown.
Use names to refer to what has come before, and how an area or a people relates to its history. The names do not have to be accurate, and should reflect myth and legend as much as fact.
Put history in the mouths of your NPCs
I don't mean they should become infodumps. If you're familiar enough with your history, you can have them naturally say things like "Not since the rule of X has Y happened," or He's a modern-day [insert famous person here]." Think about the many historical references we make: WWII, cavemen, fiddling while Rome burns... make your history live by putting it in the mouths of living NPCs the way we relate to our own history. This can be difficult to do naturally, but can be very evocative when pulled off.