One of the most captivating elements of travel through uncharted regions is the possibility of exploration leading to a useful or interesting discovery.

In order to make discoveries engaging, they should not be shown to the party directly.  Show them a sign, a clue, or some unusual observation that they can choose to pursue or not.  For example, they might see a column of dark smoke above the trees a few miles off the trail or a splattering of blood crossing their path.  Pursuing these leads will cost them travel time but could also lead to an interesting discovery.

Each day, have the most perceptive member of the party make a Wisdom (Perception) check against the discovery DC for the route.  On a success describe a discovery lead.