How to Find an Overhauled Desert Temple
The overhauled desert temple is rare, so you cannot simply wander the desert and expect to stumble onto one. You need to actively hunt for it using the map system the data pack hooks into.
Getting the Explorer Map
Vanilla desert temples are removed by this data pack, so the old trick of scanning deserts for a pyramid shape no longer works. Instead, visit a Cartographer villager and trade for a Desert Explorer Map. These maps point to the new Desert Ruins structure. Note that the relevant trade is an experimental trade, so you may need to level the Cartographer up and cycle through their offers before the desert map appears.
Following the Map and Confirming the Find
Once you have the map, open it and follow the marker like any other explorer map. When you arrive, you will not see a classic pyramid. Instead, look for a large ruined temple surrounded by a custom desert village. The village is part of the structure, so if you see unique desert buildings with workstations and suspicious sand, you are in the right place. Because the structure is rare, expect long travel distances between finds. Bring supplies, a bed, and enough blocks to bridge or dig, since the terrain around the ruins can be rough.