When were the concepts of latitude and longitude first introduced? How did cartographers determine them?
The concepts of latitude and longitude were introduced in antiquity, and our principal source for that period are the surviving books by Ptolemy (Geography and Almagest). These notions were understood long before Ptolemy, at the time of Eratosthenes, but we have very little sources on astronomy before Ptolemy.
Determining latitude is easy: all one has to measure is the altitude of Sun at noon. Or of some star at the moment of culmination. This was known (and actually performed) by Hellenistic astronomers in 3-2 centuries BC. One can use the simplest of all astronomical tools: the gnomon.
Determining longitude is much more difficult, and this was done by the ancient cartographers by estimating the distance from the travel time needed to reach one point from another. Of course all these determinations could be only very rough. The problem of longitude is equivalent to the problem of synchronizing clocks at a large distance. Before the invention of telegraph only astronomical methods were available.
Ptolemy was aware of the principle that longitude can be found from observations of Lunar eclipses (unlike Solar eclipses, they appear at the same time everywhere on Earth), but there is no ancient record of any serious attempts to do this in practice. This, and observation of star occultations (moments of covering of a star by the Moon) were the only methods available in antiquity, but they lead to large mistakes because there was no good theory of the Moon motion. For example, Columbus tried to estimate the longitude of Americas by observing a Lunar eclipse, but with no much success.
The next step was made by Galileo who discovered Jupiter's satellites, and proposed to use their eclipses by Jupiter to determine longitude. This was a very good method for cartography, but despite many attempts one could not make it work at sea (from a ship) because it requires a large telescope, and there is no way to stabilize a telescope on a ship.
Since your question is about cartography, I will skip the further development of methods suitable for observations from a ship which were developed in 18th century (Lunar distances and chronometers). But for long time even after that, the method based on Jupiter's satellites remained the most accurate method. (Transportation of a chronometer keeping good time over land is even more difficult than transportation by sea. For example, Lewis and Clark used Lunar distances when mapping North America. Lunar distances are measured by a small portable instrument, called sextant, which is much handier than a large telescope needed for Jupiter satellites.)
The method of Lunar distances is based on determining the exact position of the Moon in the sky by measuring distances from the Moon to stars. If a good, exact theory of Moon motion is available, you can find the time from the position of the Moon.
From the perspective of a cartographer, the methods based on Jupiter satellites and Lunar distances were superseded only with the advent of long-distance telegraph cables, when synchronizing clocks by telegraph became possible. This happened in the second half of 19th century. Since then, we know the longitudes of all places (where a nearby telegraph is available) with high accuracy. The first transatlantic cable was laid in 1866, and this permitted for the first time to determine longitude of places in Americas with higher accuracy then it was possible by astronomical methods.
Then, in the beginning of 20th century, radio broadcast of time signals gave a simple and convenient solution for all locations. The last step was technologies based on artificial satellites which came in the late 1970s.