It would be pretty intrusive/noticeable, since the user has to opt in to allow the site to use it. So it's probably only a risk on sites that also make legitimate use of Web Storage.
localStorage is subject to same-origin restrictions (so advertisers can't easily use it to track you across sites). And localStorage is handled like cookies when you use the private browsing mode in browsers like Firefox and Chrome, e.g.:
"When the browser goes into private browsing mode, a new, temporary database is created to store local storage data; this database is empied, and is thrown away when private browsing mode is turned off."
localStorage is subject to same-origin restrictions (so advertisers can't easily use it to track you across sites). And localStorage is handled like cookies when you use the private browsing mode in browsers like Firefox and Chrome, e.g.:
"When the browser goes into private browsing mode, a new, temporary database is created to store local storage data; this database is empied, and is thrown away when private browsing mode is turned off."
https://developer.mozilla.org/en/dom/storage#localStorage
(This is true of Flash 10.1 also, but wasn't true for older versions.)