I love games that have an engaging story that really pull the player into it. One of my most tearful moments happened in Kingdom Hearts 2 right at the end of the Roxas opening. I was also surprised that even know I've known the character for 2-3hours, I cared that much about him to shed tears.
I honestly will not play a game if the story is crap. No matter how good the gameplay is, I wouldn't be able to play it.
Other great story driven games are MGS(as mentioned, Snake Eater was my favorite, the final boss fight was so hard to do emotionally), Halo, many J-RPG's(notably Legend of Dragoon and Final Fantasy, FF8 being my favorite because I'm a sucker for a good love story). Then there is Mass Effect, never in my life have I been so concerned about how the game NPC's would think of me then when playing this game, nor have I cared so much about a cast of game characters and world. Epic storytelling.
I'd say study up storytelling by just reading. CapnBuzz has a good breakdown for how to buildup your story. My 2 cents, get your story together, think about what you want the player to experience, and design how you'll implement it into the game. In the end, have fun!