I too use pencil and paper when I really need to "think", but I think for most things a stylus is the wrong sort of input for what you want to do with a portable device.
For consumption tasks, browsing the web, etc, a touch interface is far preferable. For those tasks where touch isn't sufficient, a stylus isn't at all better. A stylus just doesn't work without the tactile response of paper (which the textured Wacom tablets can offer but a portable device can't).
That hasn't been my experience (I've been using a tablet PC for the last 3 years). With a precise digitizer and good software, stylus-on-screen writing isn't very different from that of pencil on paper. The convenience of permanence/editability/easy sharing vastly outweighs somewhat inferior tactile feel.
On the other hand, it's ridiculous that the only way to digitize these notes is by scanning, or typing them in, or using linux-unfriendly Livescribe pens that require special paper. For centuries we've interacted with documents using styluses. For doing math, for marking up papers, for scribbling notes in the margins, and for countless other activities it is simply _the_ right tool for the job. People like Steve Jobs declared unilateral war on styluses because they were being used to design suboptimal interfaces. Jobs had a point, but in rejecting the stylus outright, he threw the baby out with the bathwater.