Neil Shubin's Your inner fish (a pretty cool book, I might add) discusses this briefly in the introduction. From memory, it's a question of combining geological knowledge with knowledge of what you want to find. Basically, you're looking for rocks that are likely to preserve fossils and of the correct environment (no use looking for deep sea sediments when looking for humanoids, for example) and the correct age for the fossils you're interested in. Now that you know more or less what kind of rocks are relevant, you can look at geological maps and find places where these rocks are exposed (and not, say, buried 2000 metres below the surface).

Geologists have been studying and codifying various layers of rock and the types of fossils within them across the world for centuries. So it’s well established how old the exposed rock layers are in any particular part of the world long before they had any idea how old things are. Then as dating methods have improved we can make correspondences between these rocks and their age. So as mentioned by another commenter, paleontologists can take that knowledge of how old the rocks are, and what environment they were laid down in, and how they were formed, along with our existing knowledge of the age of various species, and their locations, and then find a likely spot with easily accessible layers from the right location and time period and conditions and they might get lucky.

Almost all of the discoveries are in the Great Rift Valley in river basins or old river basins. The combination of the geologic upheaval and erosion from the water have literally left fossils sticking out of the ground. Likewise, discoveries are found in quarries and mines. This is how the first hominid discovery was found, A. africanus in a South Africa.

The discoveries also make it seem like they just found a hominid skull, but in actuality they find hundreds of fossils (animals mostly, a few hominids) and it takes years to sort and identify the fossils. It always amazes me that the expert can take a small bone fragment and determine hominid vs deer vs monkey. Even further, which type of hominid they found, even from something like a skull fragment.

This skull was found by a goat herder, albeit a paleontology enthusiast, while digging a goat pen:

At the time, an expedition co-led by Haile-Selassie was digging at Woranso-Mille, a field site in Ethiopia’s Afar region less than three miles from Miro Dora, where Bereino was herding. According to Haile-Selassie, Bereino had tried for years to get himself hired on Haile-Selassie’s team. He sometimes claimed that fossils emerged from eroded rock; when Haile-Selassie had visited in the past, he hadn’t see any.

On this particular day, Bereino was digging an addition to a temporary goat pen when he noticed a bone exposed in the sandstone surface. Bereino got in touch with a local government official, who agreed that it might be something Haile-Selassie would find interesting.

When the official called Haile-Selassie, he remained skeptical, replying that Bereino should mark where he found the fossil and walk it over to his camp. When Bereino and the official arrived, Haile-Selassie soon realized the magnitude of the find. Bereino had found a maxilla, or upper jawbone, belonging to an ancient hominin.

https://www.nationalgeographic.com/science/2019/08/unprecede...

The corollary of this is pretty awe inspiring - we find only a fraction of a percent of the fossil record that exists, and the fossil record that exists is only a fraction of a percent of everything that happened, all the species that existed, etc.

The fact that we can still derive meaningful knowledge out of that compounded fraction of fraction of a percent is amazing; and the quantity of mind blowing things that happened that we will never get to know because they weren't "recorded" is humbling.

It also seems to imply that as discoveries on the surface dry up, we could make many more with deeper excavations.

Geologists/geology can be useful in identifying promising sediments with particular characteristics, like dried lake beds, of particular ages.

My archaeologist friend started getting into flying drones to take photos of an area of land, and then running analysis of of the imagery to pinpoint potential digging spots.

Bio Anthropologists normally in conjunction with archaeologists

brute-force is one way to find these things