The Copenhagen Interpretation seems to imply that superposition
collapses into one state once measurement has occurred, so I don't
understand how we can observe it.
In general, you should not expect interpretations of quantum mechanics to tell you anything about what you can observe. They're not physical theories. What makes them fall short of being physical theories is that they don't make predictions about observations.
Superposition, however, is a feature of quantum mechanics that is independent of any specific interpretation, and that does make definite predictions about observations. For example, we can do double-slit diffraction with particles. For an example with photons, see the photo at the beginning of section 34.4 here http://www.lightandmatter.com/html_books/lm/ch34/ch34.html#Section34.3 . For an example with neutrons, see Zeilinger et al., Rev Mod Phys 60 (1988), 1067.
Without superposition, it's hard to imagine how we could get areas of high probility and areas of low probability. We can observe these effects even under conditions in which it's only possible for a single particle to have been present at any given time.
Either the Copenhagen interpretation or the many-worlds interpretation can tell a satisfying psychological fable about why we observe these things. If the interpretations seem farfetched to you, then you're free to dispense with the interpretations, which are philosophy, not science; you will then find youself initiated into the "shut up and calculate" school. But I don't think that suffices to render the observed phenomena less counterintuitive.
I'm very accepting of the idea of there existing fundamentally
stochastic scenarios where the initial state does not entirely
determine the next state.
I'm not so sure you should accept that. Whether this is true or false probably depends on your definition of "state."