It seems to appear when you get near enough. But also in other cases, for which I can't guess a pattern yet. It could be after some time spent in the map, or after some percentage of the map has been discovered ...
It shows up when u are relatively close to the point u need to be. This range increases, as you ACTIVELY run or slay monsters in the area where the bounty has to be done.
If we go deeper: As you maybe know, Bounty Reward Experience also scales with time you are playing. There are different stages of Experience you can get (If i remember right there are 5).
As you progress in the bonus XP you progress in the range the arrow shows up, meaning if you are at bonus stage 1 you need to be very close to get the arrow, if you are at maximum, e.g. 5 you will see the arrow around the whole map.