Software Options
For software, Balsamiq is great for simplicity, Omnigraffle Pro is great for complexity (with templates from Konigi and others off of Graffletopia.com.
Sketching Is Way Better To Start With
Nothing beats sketching for getting your ideas out quickly, iterating easily, and not feeling too "in love" with creations that need to die.
Tools for Sketching
These are the tools I use, Ultra Fine Sharpies in black, red, and blue, a Fine Point Sharpie in black, and a Prismacolor Warm Grey 40% marker with broad and fine tips. That warm grey marker will take your sketching to another level in terms of communicating clearly what you mean.
Tips for Sketching
Sketching doesn't have to be fancy. Straight lines, text, a little shading … that's all you need to communicate volumes that can't be written. That said, I'll let my sketches tell the rest of the story.
Sources
Leah Buley has terrific resources on sketching and has influenced what I know. She works at Adaptive Path as a UX Designer.
Here is Adaptive Path's Favorite Tools for SketchingAdaptive Path's Favorite Tools for Sketching.
And check out Slides 16 & 25 of Leah Buley's Good Design Faster presentation.
-----UPDATE------
In order to be able to collaborate better with co-workers, and give everyone a fair shot at drawing out their ideas who might not otherwise feel artistically inclined, we use myBalsamiq and love it.