Sketching is not a required step. Starting straight in Photoshop (or even in the browser) are both valid methods too.
I'm a web designer by trade, and I almost always start on paper. Often, after starting on paper and moving to Photoshop, I come back to paper to iterate on the design before going back to Photoshop again.
I find it the quickest and easiest way to get my ideas out. I also find it a good way to weed out the bad ideas before developing them too far.
Sketching for ideation was drilled into me at Uni (Industrial Design, I think we had a class dedicated to it actually) so I assume that plays a part, but I work with and am close friends with a number of other designers of varying academic history, and their creative processes vary wildly.
You're definitely not "doing it wrong" if you don't start on paper, but it's probably worth giving it a shot as it's a reasonably low overhead to integrate into your process.
Not for me. I use a Wacom (with Illustrator, not PS, but same diff) and flipping around the the pen to erase is really no different from using a regular pencil. Except way faster.
Since I can use layers and selective editing and save off versions I feel much more relaxed doodling and exploring this way. It's trivial to save the interesting ideas while obliterating the crap.
If I really wanted to start fresh, select all -> delete is quite fast.
The big wins for pencil and paper are: ease of transport and accessibly (much simpler to carry around a sketch pad and some pencils); the tactile feedback; the resolution.
Much as with using a word processor vs. a typewriter and some Wite-Out there are interesting psychological differences at here, too.