Preloaded images are stored locally, but whether it is in the browser's normal cache or elsewhere I don't know. I really don't care where they are stored locally.
In my experience, preloaded images definitely load virtually instaneously when called in some sort of animation (image swap, slideshow etc). With non preloaded images I sometimes notice a delay in the image appearing when called because the browser downloads it from the server rather than get it locally.
I currently support IE8, IE7, FF3.6, OP9, OP10, Safari (for Windows) and Chrome. In all these browsers preloaded images, especially large ones, load very much quicker than non preloaded images in my experience.
I will always preload images that will be used in some kind of animation. Images that are not used in animations, I may or may not preload depending on the circumstances.