Travellers can be found in a town's Tavern. They have two main functions in the game. Both of these services require a fee of 30 denars.
The first is their ability to locate heroes who you have previously met but are not in your party. Note that heroes who recently abandoned you will not reappear for several in-game weeks after their abandonment, and they will be treated by the traveller as heroes who you have never met during this time.