After establishing design principles based on good assessment data, I typically turn to some quick pen-and-paper sketching to wrap my mind around design problems and areas of potential confusion. These sketches are quick, low-fidelity, and really only meant to inform small-group conversations with those closest to the project. Depending on the task at hand, I will sketch full pages, discrete interactions (such as a specific form element), or a narrative storyboard to visualize a potential user path.
Proof that you don't need to be a good drawer to be a UX Designer.
After some early design decisions with the project team, I turn toward the most important step in my prototyping process: wireframes. Wireframes effectively communicate the core content elements, visual hierarchy, and user paths present on a page while leaving out design elements like colors, font choice, graphics, and aesthetic detail. At this phase of a project, wireframes helpfully guides feedback toward user and organizational needs rather than allowing conversation to wallow in arguments over color choice or image selection. I use the online tool Mockingbird for wireframe creation, since it allows for lots of flexibility and sharing possibilities without letting me dwell on pixel perfection. There are lots of other tools in this arena if Mockingbird doesn’t fit your style or workflow.
The Virgo home page wireframe exemplifies the "Re-thinking Home" and "Easy Decisions First" design principles.
In the presentation below, you’ll see how I present these wireframes to our stakeholder population. I will almost always re-present the project’s design principles first to help frame discussion, then talk through each image and explain design decisions in terms of those design principles and other established user requirements.
After discussion of the wireframes and incorporation of any salient feedback, I move on to the final design (usually in HTML & CSS instead of a graphics tool like Photoshop), which is much more likely to earn acceptance after our early and frequent communications with stakeholders. In this instance, the final Virgo design had some important differences from the presented version, based on data acquired during later usability testing. Most notably, we added a “Switch to:” bar just above search results to give users an easy route to switch their search “stream” on the fly (example).
Library User Experience 
This is really very helpful, Joe– thanks for putting up these examples, in addition to those I saw in your talk. The whole thing is so so smart. I’m trying Mockingbird to wireframe for my whiteboarding session tomorrow, if you are interested– will be at 3 pm in the Scholars’ Lab grad lounge, I believe.