A recovery is the attempt to return on-stage after being knocked off. Some tools to achieve this end are the second jump and the third jump (usually an up B attack).
Percentage recovered in the Brawl records refers to the amount that a character recovers from eating food or picking up a Maxim Tomato or Heart Container. Basically, it's the amount that they recovered from using a healing item.