I think mercenaries are randomly generated where and when you would expect them based on the unit file (e.g. Alans around the black sea; gunpowder units in high), but disbanded units also join the merc pool. Mercenaries are constantly on the move and appear where there are few law-related buildings (palaces and title-related buildings, town watch, perhaps the border forts); if a war is waged nearby and where mercenaries have been hired before.