Well first things first make sure you have built an inn and this isnt sure to get your mercaenaries, you cant control when mercenaries appear in what province and what kind of merc's they are. When they did appear though when you select what merc's you want make sure you click hire on the merc's menu after youve clicked on them and the mercs will be yours.

The best places in the empire to find them is trebizond and constantinople, trebizond though starts with a inn so you should have mercs thee.