Bastion box art obtained via Wikipedia
Right from the very start of the game, a rustic voice belonging to a sage old man describes your actions and the game world. The wording would probably be suitable for a short story, it's that good. Not only that, but it's varied enough that you don't feel like you hear the same thing over and over.
And the technology to make it happen? Certainly nothing complicated. The logic would be pretty straightforward, especially given the constrained nature of the isometric 2D play space. When the player falls off the edge, a related quip is spoken. As the player moves into a certain area with predefined enemies, background on why he is there is given. Small mementos left in the world can be gathered, and the player can ask for a piece of their back stories later on.
It doesn't hurt that the voice acting and, like Skyward Sword, the music are top notch.
Have you played some or all of Bastion? What was your experience? What other games have fantastic storytelling that was likely accomplished with relatively simple technology?