Well... first the world needs to have an ancient history to call on. If you haven't given the world a history, you'll need different strategies to give the impression of one. 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. I'll move forward assuming your world has a history and you're looking at how to express it.
Physically layer the settings
What is now got 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? Making those catalysts significant to the story or the setting beyond their obvious physical changes will make the history tighter and the world more real.
Name things for people and events that have come before
Use names to refer to history, and how an area or a people relates to that history. The names do not have to be accurate, and should reflect myth and legend as much as fact.
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 (Washington DC), victories (Trafalgar Square), and sponsors (Jamestown).
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.