First off, storytelling games are generally (not always, but generally) a subset of RPGs so I don't think it's one or the other. From my experience, 'storytelling game' is not so much a strict, technically defined term applied to RPGs as much as it is a sort of loose category. Games I usually hear defined as 'storytelling' are Monsters and Other Childish Things, Blazing Rose, Trail of Chthulu and then depending on who you ask, Feng Shui, Spirit of the Century, Dogs in the Vineyard and anything put out by Luke Crane. They do have some common features, though, that are worth mentioning:
1) Minimal mechanical growth: most characters in 'storytelling games' don't experience a lot of solid mechanical increase - levels, stats, etc. There are a few bumps here and there, but it's nothing compared to D&D, GURPS, RIFTS, etc.
2) "Pass the Stick" mechanic - 'storytelling games' often have a core mechanic that structures how much input players have in the narrative rather than characters in the game world. In Shadowrun, I kick down the door in time to stop 'generic terrible event' from happening to my love interest only if my character has enough Strength. In Blazing Rose, I can do it because I as a player won the most recent trick (card-based system) and so I get to resolve the conflict.
3) Disregard for 'physics': This is sort of the natural outcome of (2). In order to have a cloak that deflects missiles in D&D, I have to find the specific magic Cloak of Missile Deflection. In Dogs in the Vineyard, my ratty old jacket can bounce bullets because I have the plot power to say it does. The next time, I might decide the shot tears a hole in the very same cloak hit in the same spot. In GURPS, I might need three or more separate skills to make a flipkick attack by planting my hands on the enemy's head, springing over him and kicking him in the base of the skull on my way down. In Feng Shui, not only do I not need any specific skills, I get bonuses to the attack for describing in detail the way it's executed.
Hope that helps.