Your main question:
What are [a] planetary governor's methods of finding Psykers?
A Planetary Governor should normally have access to the following resources to conduct this absolutely necessary component of Imperial Governorship: Planetary Defense Force (direct command), Adeptus Arbites (independent), Adeptus Astra Telepathica (liaised to Planet Govs for communication). This should be true of all worlds that have an actual Planetary Governor, regardless of size, since all Imperial Worlds need to be able to defend themselves, guard against internal corruption, and communicate with the greater Imperium (respectively). Even with only these "bare-essentials" Adepta, a prudent Planetary Governor should be able to have at least one Psyker available to Psyniscience check for others. As noted in Alkano's answer, one of the better ways to screen for this is through spaceport customs.
There could also be other Imperial factions involved with a given planet's Psyker-gathering activities:
The Adepta Sororitas and Adeptus Ministorum may well just purge with fire anything they even suspect might have the stain of the witch.
The Imperial Guard actively uses Sanctioned Psykers, but given their rep among general troops, IG reactions could run the gamut from Sisters of Battle-level zeal to legitimate sympathy.
Adeptus Astartes gather Psykers to be Librarians, but they generally don't take from planets that have Planetary Governors, since they have their own worlds to recruit from.
Adeptus Mechanicus is outwardly nominally afraid of Psykers, since most cogboys who get involved with Warp-anything go the route of the heretek-al Dark Mechanicus and/or are censured.
Inquisition has the entire Ordo Hereticus dedicated to hunting down Psykers, along with the assistance of their Chamber Militant, the aforementioned Sisters of Battle.
I know that in Dark Heresy 1e and 2e you can use the Skill 'Psyniscience' to detect changes in the Warp. Here's the entry for it from Black Crusade Core Rulebook, page 107:
PSYNISCIENCE (PERCEPTION)
Those with the Psyniscience Skill sense the currents and eddies of the Warp and Immaterium. Characters can use the Skill to detect the presence or absence of daemons, the use of psychic powers, psychic phenomena, disturbances, or areas where the flow of the Immaterium has been unsettled or disrupted. Unless otherwise noted a character can use the Psyniscience Skill to detect entities, locales, and events up to a number of kilometers away equal to their Perception Bonus. A GM may increase this range for particularly powerful events or creatures. The general results of Psyniscience tests are summarised on Table 3-4: Psyniscience (same page: 106).
Skill Use: Full Action
1 DoS: Awareness of Immaterium disruption or number of entities present
2 DoS: Approximate direction of the phenomena or creatures
3 DoS: Rough location of the Warp creatures or beings affecting the Immaterium
4+ DoS: Exact position of the creatures or psykers present
I don't know what the standard distribution birth rate of Psykers is in the Imperium, so it would be difficult to answer how many are likely to be found wherever it is that your game is taking place. However, as you stated, the Imperial Tithe requires that each planet under the control of the Imperium does three main things, one of them being the gathering of Psykers.
Every Imperial planet must agree to turn over or mercilessly slaughter with malice aforethought all unsanctioned psykers. The reasoning behind this is that without (and sometimes even with) the divine sanctioning of the holy Emperor, even the most well-meaning psyker can accidentally become a conduit for a Realspace/Warp invasion. Entire planets can be and have been lost because of one errant soul that slipped through the dragnet. Needless to say, this is a massive problem, and it's better to have a few false positives rounded up and killed by your paranoid, uneducated populace over losing entire cities/continents/planets to a phenomena.
At the same time, the more people on the planet, the more likely you'll find a Psyker. If you assume that the same birth rate for Psykers occurs everywhere, then the best place to hunt for and find Psykers would probably be Hive Worlds, as a team of Psykers with good Psyniscience and Perception could probably canvas the entire cloud-scraping city relatively quickly. Given that this is also a requirement, and I'd assume that most hive cities already have some sort of protocol in place for culling and finding Psykers.
Lastly, it seems to me in the fluff that people suspected of being Psykers are often killed by the people around them before they have a chance to manifest something terrible. Sometimes the issue is that they are found and safely captured, but holding them until the Black Ships arrive takes too long, and something bad happens instead. Knowing the level of sensitivity that the average Psyker now has with regards to the Psyniscience Skill, I feel like tracking an active and/or powerful Psyker through even a hive city wouldn't actually be that hard.