This post is based around my experience as a GM and from my experience only
As I see it, there are three ways to change it: Rewards in terms of advancements (XP, Gear, etc), rewards in terms of bennies and the like and rewards in terms of compliments. While I'm strictly against rewards in the form of advancements, I really like the other 2 types.
XP and the like
An XP reward is a great tool for the short term. In the short term it will make the players happy that they chose a particular way of action, while also making them crave for more. I see with it 2 main problems that detract from it and turn it into a damaging gaming nightmare.
The first one is that it is not that different from bribing the players. Instead of promising the players money we're promising them to level up faster and more often. Personally, I have a slight problem with bribing my players as my sense of morality prevents me from doing so.
The second problem is that by teaching them that "good actions" equal XP rewards, we teach them that things that don't grant XP are bad things. This is far more problematic than it sounds because it a) prevents us from ever stopping rewarding the players, so no real progress has been made, and b) discourage players from coming with things of their own as we don't reward them for their style of play. Furthermore, we won't see those beautiful actions like the ones done by players who add a little sparkle of detail here or there, for example.
Bennies and the like
The little benny is a beautiful thing, both pretty and charming. When used right, it can reward in ways that are far greater than most other ways can, but when used wrong it can destroy stories. Although this danger, I still think that it is a great tool, when used right.
The most important thing to consider when adding bennies, as far as I can see, is that the players will have most of the power to grant it. I truly believe that there's no one who knows better when the players have fun than the players themselves, and as such they shall grant it.
Saying that, I use a little different approach, which is still quiet close, but not exactly the same: It's a system that I borrowed from a great indie RPG called Awesome which states something like that, when implemented into my games: "If at least one player think this was cool or fun or anything of the like, the action succeeds. If the entire table thinks it was cool or fun or entertaining then the action succeeds and another good thing happens."
If there is something that will make me, personally, less selfish in my gaming (and far better overall) it will be without any doubt a compliment. Be it from a player or from the GM, saying that something that I did helped to make the game for them will make me craving for doing that again. When they think that I'm cool, I'm cool and when they think that I help to make the game, it's exactly what I do.
In other words, try saying to your players when they did good stuff that it was cool or fun or entertaining or even all of the above. It will surely make a difference.
One last thing
To that I can only add a seconding to Carl:
Failure has to be "fun." If failure is not-fun, then players will do their best to avoid failure, and one's own failure is more not-fun than another player's.
Making failures fun is one of the greatest tools in order to achieve this aim.