How can you tell a Story in Minecraft?!?
Well. . . these guys have been dong a pretty good job.
Element Animation Minecraft Shorts:
Or for something with a little more narrative. . .
I think the last link is an excellent example of how storytelling can be achieved in the Minecraft world (The egg character wont make much sense unless you're familiar with Element Animation's Story) So I'm looking very forward to seeing what Telltale Games does with this franchise! Also if there are any villagers in the game, I would love it if Dan Lloyd did the voices, heh heh.