To recruit you must be somewhere with an oversupply of manpower. Most towns and cities should do just fine, as will some villages. A town or city near a war front may already have every able-bodied person already conscripted into the army.
Each attempt at recruitment costs d6 x 100gp (as suggested in Holmes) but this covers both the costs of the recruitment process and the initial cost of hiring the NPCs rolled below. If you come up short on cash (e.g. you roll a 5 and only have 423gp) subtract one from your d6 roll below for each 100gp or fraction thereof you are short.
d6 Roll Result of Recruitment
2 or less Hopeless Loser: 0 level forever, no particular skills
3 Likely Lad/Lass: 0 level, but at the end of every session survived roll 1d6, on a 1 they join a class
4 Specialist: roll 1d6, 1) cook/brewer 2) pack animal handler & packing expert 3) equipment maintenance & repair expert 4) herbalist/hedge doctor 5) horse tender 6) generally competent dogsbody
5 d6 mercenaries (in Wessex these will tend to be Welsh bowmen or Flemish crossbowmen)
6 1st level adventurer: roll 1d6, 1-2) Fighter 3) MU 4) Thief 5) Cleric 6) Halfling
In general the PC will need to supply appropriate equipment, though mercenaries and adventurers have a 2 in 6 chance of possessing some basic gear and a hedge doctor will usually start with a supply of herbs and bandages.
Recruited first level adventurers will generally expect a half share of the treasure while mercenaries will expect cash bonuses when rendering extraordinary service, such as fighting horrible inhuman monsters. Past these requirements, henchmen and hirelings are paid on a quarterly basis. On each Quarter Day the employer must roll a new d6 x 100gp for each henchman/hireling and either pay them that much or dismiss the henchman/hireling from service. The traditional Quarter Days are Lady Day, Midsummer Day, Michaelmas and Christmas, which fall on March 25, June 24, September 29 and December 25.
If the date of recruitment is too close to an upcoming Quarter Day for the prospective employer's comfort, you can offer to hire the NPC on Cross-Quarter Day terms. The Cross-Quarter Days fall roughly in between the Quarter Days. They are Candlemas (February 2), May Day (May 1), Lammas (August 1) and All Saints Day (November 1). In order to hire on these terms the employer must roll a reaction check. An unfavorable result indicates that offer is refused and the PC is out the money spent on recruitment. If the offer is accepted expect a lot of grumbling on Quarter Days when all the hireling's friends are getting paid, especially at Christmas.
Players generally run their hirelings but all the usual admonitions about abusing hirelings and the rules for hireling morale and loyalty still apply.