While the pronunciation of str- as /ʃtʃr/ or /ʃtr/ (shtr-) is fairly common, it is less common than the simpler cases that generally go unremarked.
The reason behind this pronunciation is a phonetic process called Assimilation of Place of Articulation. In this case, the –r- sound is pronounced farther back in the mouth than the preceding sounds. The effect of the place of articulation of the r sound is that, in some contexts, its place of articulation can be assimilated by the preceding sounds. In the case of more forward consonants, they can be moved further back in the mouth. When that happens to the s sound, it can become /ʃ/ (sh).
The simpler case, which goes nearly completely unnoticed, is the case of tr- (and dr-). The sounds for tr- and dr- are even more widely palatalized than str-. So almost all of us pronounce train, treat, trim, trolley, truck as /tʃ/ (ch), as if they were spelled chrain, chreat, chrim, chrolley, chruck. The same is true of dr-: we pronounce drank, dream, drill, droll, drunk with palatalized d- or /dʒ/.
If you were to pronounce the d of drunk exactly as you do the d of dunk, you would sound foreign. Likewise with the t of truck vs. tuck.
But almost nobody remarks these allophones of t and d, which are just as remarkable and (not so) shtrange as str-.
Have you noticed this pronouciation to be more common in the Mid-Atlantic states, in particular Philadelphia and Baltimore? Philadelphia is the first place I hear this pronounciation (shtr).
It is certainly common in Philadelphia and New York. I can't really speak to Baltimore.
Since posting this, I have noted a podcast with a speaker native to Atlanta, Georgia use the chr- pronunciation of tr-. I have also heard English folk use the chr- pronunciation (locale unknown), someone from Sydney, and a speaker from Bakersfield, CA.
Since it is a physical phenomenon, it is quite widespread throughout the anglophone world.