Story is pretty difficult, cos you don't know it's a good story until after you've played it....
Personally I rely on reviews and reading people's opinions and discussions on gaming forums. Ill also admit that I'm a bit of a graphics whore. A pretty game is easily sold to me.