Right before Elsa freezes, she shoots that message into the air with ice magic, calls out for Anna, and that snow message finds Anna. Anna recognizes her grandfather and puts some things together. She knows the stories and recognizes the characters.
Yep, this. How exactly is that hard to follow? It makes perfect sense. I guess someone wasn't paying much attention...