How to lay of underlayment for a cedar shingle roof
For an unheated tool shed, you don't need the 3ft wide course of underlayment. Over a heated house, that 3ft course should be a rubbery waterproof ice barrier that seals around nails, so if an ice dam forms, water will not back up and leak through. Just run one course of the narrow paper, sticking out so that it will hang into the gutter a bit, then a starter course of shingles. If your shingles are 18" and exposure is 7", then run your next strip of paper 7.5" to 8" up from the bottom, then add your 2nd layer of shingles for the double starter course, then paper/shingles/paper/shingles to the top, ensuring that the paper never shows. That would be 14.5 to 15" up from the butt of each shingle course.

This article covers the subject quite well, and I even learned the term "interlayment" for those 18" strips of tar paper:

http://www.nachi.org/wood-shakes-shingles-part3-135.htm

(I'm in Vancouver, and just re-did my tool shed roof the same way.)