Very fun! Some of my most memorable trips have been in wickiups and lean-to shelters!
First, get Tom Brown's Guide to Wilderness Survival for an excellent summary on survival shelters.
Next, keep it simple and small- my personal fav is a wickiup in non-snow situations. Also, bring along a tarp as well- it is really, really difficult to make a waterproof shelter from natural materials. More than once, a small tarp on top of the shelter kept me dry through the night.
Tools- nada. I usually had a pocketknife but even that is unnecessary for a small, short-term shelter.
Last, in following Leave No Trace, this is not ethical in regular backpacking areas because you'll have to gather too much in the way of natural materials. Find an off-trail and out of the way spot below the treeline area for your shelter. You might not be at your favorite lake, but that's the beauty of a trip like this- getting back to something more primal. And you'd want to have that campfire anyway...
Have a great trip!