Recent travel history is mostly recorded electronically. The further you go back though, the more likely it is that an electronic record does not exist.
It really depends on the country and I would say that this question is too broad to give an answer that covers all nations for the past who-knows-how-many-years.
The main answer though is that each country records travel history from its own perspective. They can get each date someone entered and exited with the name and passport number used. When you change passports, in most countries you get a new number, so they must rely on other data to make a match which is not entirely reliable. However, they are unlikely to know your travel history outside of the country.
A country does not even necessarily known where you are arriving from since airlines do not always send passenger data to immigration. For example, here in Ecuador, they know the entry and exist of each person but if you look up travel history records, the origin will often be stated as the nation of the passport used to enter, even if that is not actually the case.
A few countries have no exit immigration. US, Canada and the UK, as far as I know, so they rely on external data to know when people leave. With exits via passenger airlines, this data tends to be very reliable but when exiting by land or water, exit information is rather spotty. There are countries with no border controls, some with controls between at some borders, so there are many places where travel history simply cannot be tracked.
Some countries and regions share data between them so they can know about travel history outside their country but this is more of an exception than the norm.