When you hit the shuffle button again, does it (...)

When you shuffle again, its behavior depends on the shuffle mode you selected.

(Note that pressing the 0 key on the remote will toggle to the last shuffle mode.)

If your last shuffle mode was "random", then when you shuffle again, it will be a random re-shuffling from scratch. If the shuffle mode was "least recently played" then it will weight the things you already heard towards the bottom of the shuffle.

PS. When you shuffle by "least often played", it seems like it doesn't necessarily play all "zero-played" songs first, but tries to generally put them in front according to some weighted algorithm...is this what's really happening?

Correct. It's a weighted shuffle, not an absolute ordering.

Note that the "weight" factor for "least recently played" has a fairly short memory. 12 or 14 days if I recall. So anything you heard two weeks ago is considered "ages ago" and is fair game for the top of the shuflle. This was discussed in another recent thread where I expressed my personal opinion that this was a bug and not a feature.