It was in Melee, and we ignored. Now in Brawl, Sakurai has made it to where we can't ignore it any longer. Stale-Move Negation is when moves weaken in both damage and knock back when used in succession. How does it work exactly? Sakurai didn't want to get to technical on the Dojo, so it looks like we'll have to pick up the slack.
I'll start with a few quick facts and then move into the real scientific/research/data portion.
- Moves weaken even after one use
- By using other moves the strength of moves can return
- Damage is calculated by fractions even though the damage is displayed as a whole number percentage
- As a general rule, an attack must hit an opponent and do damage to both weaken and sharpen
- Each input of an attack command counts as 1 hit towards sharpening
- Each throw, punching after grabbing, and successfully landed projectiles can both weaken and sharpen
- Multi hitting attacks only count as 1 hit, but the 1-2-3 neutral punch combo counts as 3 (because of the 3 separate A button inputs).
- To sharpen one move from any amount of decay, at least 9 hits from other attacks must be successfully landed
- A move recovers strength (sharpens) by a percentage amount. This means it'll take 9 hits from other attacks to fully restore an attack whether or not it was fully weakened or barely weakened.
- Dying resets all depreciated values on all moves. If you're at high damage and you don't want to die, I suggest avoiding the opponents kill moves. However, their moves will only weaken individually and only when they successfully hit you. So, you'll be fighting a pretty dangerous battle from then onward.
I ran a couple of tests using Kirby's moves on Dedede. Here's some of the results.
Kirby hammer ground (side + B) 
damage % [blue data]
24 100%
20 83%
18 75%
16 67%
15 63%
13 54%
12 50%
12 50%
11 46%
10 42%
11 46%
10 42%
The more damage a move does, the smoother the curve of course. But, as you can see, the cure is consistent between four of Kirby's moves: hammer (blue) rock (red), forward smash (yellow), forward tilt (green).
Next, I used Kirby's jab attack to sharpen my hammer attack that I had reduced to 10 damage (the absolute lowest damage for the move). This chart compares the decay rate with the sharpening rate.
As you can see, the two curves meet at 70%, which is about 17 % of damage. This is the value that all moves will hover at if the move is used every other move.
In the next chart, I test the values of two moves simultaneous.
The hammer (blue) and the forward smash (red) reach approximately 70% at the same time. In this test, the hammer was at it's absolute weakest, and the forward smash was at it's strongest.
This means, the weakest you can make two moves is 70% of their original strength. If you try to weaken 3 moves, the percentage only climbs.
Ultimately, in Brawl, players can only significantly weaken one move in their arsenal. Because knock back is also reduce, new combos can emerge. Try weakening Marth's forward air by using it 9 times in a row. Then try pulling off a forward air into a forward smash combo. Because the dynamics of weight and knockback and damage are in flux, becoming a master of one's character is deeper than ever.
Remember though, it is possible to significantly reduce the damage/knock back potential of several moves. Though all the decay curves are almost the same, some moves lose their edge more quickly and apparently than others.
Really, all you need to remember at this early stage in Brawl's life is... if you want to deliver more than one of your most powerful blows with a single attack, make sure you find 9 hits in between uses.
For the future: I have not tested how Pokemon Trainer, Zelda/Shiek, or Samus/Zamus's transformations affect stale-move negation.