So, is the tweak recursive? If I'm listening to REM and press "Artist", does it go through the entire running order and swap each REM song it finds, one after another, to be immediately after the one I'm listening to?

Yes, but remember that each press of the tweak button only adds one song. If you have 50 upcoming REM songs, you'd have to press the tweak button 50 times to stack them all up.

Tweak is mainly meant for "Oh, that's an REM tune. I want to hear one or two more REM tunes before continuing on with the shuffle."

If you really want to hear all of your REM albums, what you should really do is un-shuffle. Then you can re-shuffle when you get tired of listening to REM.

Say I'm listening to my shuffle playlist, and I get to an REM song, so I press "Artist", and it then stacks my 9 REM albums back to back in shuffled order after the song I'm listening to. So, after I hear 6 REM songs, I want to go back to the random order (ensuring that I don't re-hear the songs I've already listened to). How is this possible?

You shouldn't be using the artist tweak to stack up your entire REM collection because it would take so many button presses. You should shuffle and unshuffle instead. However, if you did do what you describe and got tired of REM, you could press and hold the artist tweak button to drop all the REM songs as described here.

Now, in your last thing you said specifically I want to go back to the random order (ensuring that I don't re-hear the songs I've already listened to). When unshuffling and reshuffling like I describe, I really have never had a problem with this. There are enough tunes on my player that in a given sitting, I rarely hear a repeated tune after reshuffling. But if you want to be absolutely religious about it, then simply use the Least Recently Played shuffle mode.