Here's an Imgur album I made showing darkroom sky replacement with litho masks. It's the most precise way I've found to do this - only special gear needed is an everyday three-hole paper punch and 2 silkscreen pins that match the hole sizes (from Ternes-Burton). It's less complex that you'd think and in many cases you can mask very fine detail with no haloes at all.
Time Rudmans "Master Printing Course" has some excellent and clearly explained techniques for this (though none will let you mask things like tree branches as well as litho film, which does require the right neg to really work well). My favorite printing book ever, too.
it's worked so well that I've started packing a blue filter for when I see a cool scene with a dead-blue sky, to give me a very light BG and allow for sky replacement masks. A big curse of Texas is the no-clouds-all-summer environment.