In order to reach Paititi, Lara has to solve four Puzzles: The Trail of the Eagle, the Trail of the Snake, the Trail of the Spider, and the Trial of the Jaguar. These puzzles, serving as the only entrance to Paititi, are the main reason that no one from the rest of the world has ever been able to get there so far.
The city of Paititi was believed to be located in Brazil, but in the scene in the La Casa Mexicana, a restaurant in Cozumel, Mexico, Lara explains to Jonah that because of the misreading of a Maya date and the resulting error due to the earth's precession it actually can be found in Peru.
From the E3 gamplay videos, we further know that, when Lara and Jonah fly to Peru, they discover a valley with a city in it. If this actually is Paititi is as of now unknown.
There are a lot of different people and animals that can be found in Paititi. It is the biggest hub space in Shadow of the Tomb Raider with lots of Merchants, Mission Givers, and just normal people that to populate the busy markets and workplaces. Many of these Lara can interact with, like a small child she can hug or just people she can talk to to lean more of the history and background of Paititi.