What would you do to trail mark?
Here are some trail signs you can leave using natural materials:
Image from the Scouts Canada Wiki article on Trail SignsThis image is taken from the Scouts Canada Fieldbook & similar information is in the Cub Book. An activity we've done with our Cubs in the past is have the different sixes go off and make their own trail using these markings and then have the other sixes try to follow them from beginning to the end.
Regarding what Grylls did in his shows, I don't recall specifically, but it was something similar to the above.