The counter begins when you first start your game. You get an advancement every time you walk 128 steps. Of course, it should go without saying that those advancements don't carry over between continues, but the step counter does.
It applies to everything.
Wouldn't that mean I would've had to keep track of every step I've made since I started the game? Which in other words, I would've advanced an uncountable number of steps, unpredictably changing the IV frame and therefore making it impossible to RNG my entralink pokemon?!
That couldn't be the case, because I've RNGed shiny legendary pokemon on IV frame 1 with no problems. Why would something like that be the case with entralink pokemon? I'm really confused here.