To recruit henchmen, you must be in a town or city.
Spend 1 week posting notices and spreading the word (the actual work is done by the SELL SWORDS GUILD if you recruit in Polychronopolis.
For each 100gp you spend, 1d6 candidates will show up, to a maximum of 10d6 in Polychronopolis, 3d6 in Shadar, 2d6 in Portburg or 1d6 in Farmington.
The offer of Livery and Maintenance, usually some additional upfront equipment and a treasure share is required and then the PC must make a CHA d20 check, which, if it passes means that the henchman joins up with the PC. For each 50gp in cash (which they will immediately spend on debts and family obligations if they accept) you offer, add +1 to your CHA for the recruiting roll.
Those with Recruiting Skill can take 1 week, spend no recruiting money, make a skill check and find a recruit with exactly the class, species and skills desired, instead of a general draw of candidates.
Henchmen will come with minimal equipment, typically no armor and one cheap weapon. Clerics will have a wooden holy symbol and Magic-Users a spellbook. They are poor, that’s why they’re working for you.