I carry a couple of cheap Bic style lighters (mine came from the 99Cent store) and a box of REI stormproof matches. I highly recommend the matches-they burn like a sparkler, even when wet because they are coated with a similar compound -
http://www.rei.com/product/617046/rei-stormproof-matches

Also, get an old school film canister-the plastic ones or a similar container, take cotton balls, soak them in Vaseline and stuff them in the canister. Great fire starter. I also have a sparker I got at REI, easy to use. I haven't actually started a fire with it yet, but it puts out a big shower of sparks. One of these-
http://www.rei.com/product/783662/ultimate-survival-technologies-sparkie-fire-starter

There are a bunch of videos on YouTube on how to use this one and many other fire starters-
http://www.youtube.com/results?search_qu...1l0.4.3.5-1l8l0

You could put all this stuff in a small kit in a plastic bag inside a small belt pack so that the kit isn't in his pack, but on his person in case he gets separated from the pack-it happens.

There is a Jack London short story called "To Start A Fire" about a guy who gets lost and freezes to death in Alaska because he can't start a fire. Worth reading, if a bit depressing.