My impression is that it depends on the phone, the OS, and on whether there is a corresponding web application at all (let alone whether it supports mobile sync).
Assuming my impression is correct, and I really really want local storage and web synchronization, I think that means there aren't many options out there. I have mentioned http://notespark.com before on here; it is for the iPhone and I am pretty sure it supports full sync between the iPhone and my web-based data.
So am I correct, or are there actually a lot of options for this local storage/web sync capability and it is just a matter of choosing between features?
At this point, the iPhone has the most options. There are a lot of free or cheap iPhone programs that have only local storage. However, there are several decent options in the notes and todo categories that have web and local storage. Notespark is ok for smallish notes. Evernote is a real heavyweight, and what I use for most things. There are many others, though. A lot of programs sync or at least backup to Google docs. For todo's, you might look at Toodledo and Remember the Milk on the web. There are several programs on the iPhone that interface to each. I can't comment on specific programs for the Pre or android phones.