Recovery is not limited to one's Up-B. For many characters, there are many ways to augment the recovery.
Bowser
In theory, Bowser's Flying Slam (only in SSBB) could, if he grabbed onto a character in midair, propel him up, possibly to safety.
Captain Falcon
In SSBM, the Falcon Kick would allow Falcon to regain his 2nd jump in midair, and move him forward somewhat. Raptor Boost is also a good horizontal recovery move, even moreso in Brawl where it bounces up upon striking.
Charizard
Because of Charizard's wings, he has multiple mid-air jumps, and can glide.
Diddy Kong
Diddy Kong can use his side B to move forward a fairly large distance. If an opponent is coming towards you when you are recovering, use Monkey Flip to grab onto them, then press up to leap off of them for a great jump. He can also wall cling.
Donkey Kong
Donkey Kong's Headbutt slows momentum.
Dr. Mario
Dr. Mario can use the Cape (technically the Super Sheet) to propel himself forward a bit. Also, if he rapidly presses B during the Dr. Tornado, he rises up in the air.
Falco
The Falco Phantasm moves Falco forward, and should always be used to recover when above the stage; indeed, that is its primary use.
Fox
The same goes for the Fox Illusion as for the Falco Phantasm. In addition, his Reflector stops vertical movement.
Ganondorf
See Ganondorf: Recovery.
Ice Climbers
Belay is an incredible recovery move when both Climbers are present. Use Squall Hammer and press B rapidly, and you will rise into the air. This is basically your sole recovery move when Nana has been KO'd, but it works better when she is present.
Ike
Ike's Quick Draw can be charged, and moves him forward quite a bit. Use it to augment the poor horizontal recovery of Aether.
Ivysaur
Ivysaur's U-Air and D-Air either propel him downward or upward respectively. Though it can confuse edgehoggers, the boosts are both very small. Unfortunately, you cannot change Pokemon in midair, thus preventing you from using Charizard's good recovery.
Jigglypuff
See Jigglypuff: Recovery.
King Dedede
King Dedede has no supplementary techniques for his recovery; however, he hardly needs any (see King Dedede: Pros).
Kirby
Kirby already has phenomenal recovery, but in addition to his 6 jumps, Hammer moves him forward a bit in both Melee, and Brawl, and Final Cutter can be used as a last resort for vertical recovery.
Link
Link has a variety of techniques to augment his poor recovery. Link's bomb, if it explodes while he is holding it, can aid his recovery by giving him back his Spin Attack (see Bomb recovery). Also, in SSBM, the Hookshot grabs onto walls, and in SSBB, the Clawshot (its replacement) is a Tether Recovery.
Lucario
Interestingly, Lucario's dair stops all momentum, making it easier to recover. Its recovery is also "bendable". Lucario also possesses a unique trait, the ability to wall jump after using his third jump. This only takes effect if Lucario reaches the wall before Extremespeed ends and is very useful on stages with space to wall jump under the ledge, such as Final Destination (SSBB)
Lucas
Lucas has multiple recovery options: the standard PK Thunder, his Rope Snake, which is also his grab, Zapjump, Magnet Pull, and Wave Zap. He can also use his PSI Magnet to hover in the air, combatting edgeguarders. Also, Lucas' PK Thunder travels through enemies (as opposed to Ness'), and is harder to guard against.
Luigi
Luigi's Green Missile, combined with the mobility of the Luigi Cyclone, give a hard-to-match horizontal recovery. In addition, both moves can be used in combination with Super Jump Punch, since neither of the two makes Luigi helpless.
Mario
Mario can use the Cape to propel himself forward a bit. Also, if he rapidly presses B during the Mario Tornado, in SSB and SSBM, he rises up in the air. This does not work in Brawl, as it is a dair. Additionally, by using F.L.U.D.D. fully charged in the opposite direction if where you want to go, the recoil will push Mario back somewhat.
Marth
Marth is able to continuously tap forward special combos and then use the Up Special attack when directly under the stage to recover himself. This works best on Final Destination. In Brawl, charging his Neutral Special Move, the Shield Breaker, to its fullest will cause Marth to fly forward at a quick speed.
Metaknight
Metaknight has an exceptional recovery. His wings give him multiple mid-air jumps and the ability to glide. In addition, all of his Specials can be his final jump. (Unfortunately, all of them put him into helplessness.) Use Shuttle Loop for vertical recovery, and Drill Rush for horizontal. Mach Tornado may be good against edgehoggers, and Dimensional Cape could be used to launch a surprise attack.
Mewtwo
Mewtwo has great jumping capabilities, so usually he has no need of techniques to help him recover. However, if you fire a fully charged Shadow Ball in the opposite direction if where you want to go, the recoil will push Mewtwo back somewhat. Confusion cancels momentum.
Mr. Game and Watch
In Melee, G&W has no advanced recovery techniques. However, in Brawl, after he uses Fire, he floats down by parachute. You can alternate between falling at normal speed and by parachute by using aerials.
Ness
Ness can combat edgeguarders by hovering in the air with PSI Magnet, just like Lucas can. However, Ness' version doesn't cause any damage.
Peach
Peach has a plethora of techniques to help her recovery. For instance, the float allows her to move horizontally without falling while in midair. Also, her Peach Bomber allows her to scale vertical walls. It can also be used to stall matches, though this is banned. Even after all this, when she uses her parasol, she falls much slower.
Pichu
Pichu's Skull Bash allows him to get great horizontal distance, giving him an above-average recovery.
Pikachu
The same rules apply for Pikachu's Skull Bash as for Pichu's - except Pikachu doesn't take damage from it.
Pikmin and Olimar
You must always have 6 Pikmin as Olimar if possible. The amount of Pikmin you have directly affects the length of your Pikmin Chain, a tether recovery. However, if your opponent wants to edgehog you, try throwing a Pikmin - preferably purple - at him/her, as edgehogs are deadly to tether recoveries.
Pit
Pit has wings; thus, he has multiple mid-air jumps and can glide. He has an incredible recovery, as seen here. In addition, his Angel Ring pushes him forward slightly.
R.O.B.
ROB has an incredible Up-Special, which can be used for some time in midair. Also, his bair and Arm Rotor move him forward a bit, augmenting his recovery. The Arm Rotor, however, generally has far too much lag to help him a lot. The ideal recovery pattern is a small boost of Up-B, followed by a b-air, repeated as much as is possible.
Roy
See Marth except for the Shield breaker strategy.
Samus
Samus's Bombs can be used to help her recovery (see Bomb recovery). Additionally, her Grapple Beam could grab onto walls in SSBM, and in SSBB, is a tether recovery.
Sheik
Sheik's Chain is a tether recovery in SSBB. Additionally, some people will switch from Sheik to Zelda for her better recovery.
Solid Snake
By using Snake's Down B and then immediately pressing Down B again (his remote control C4 explosive) you can potentially blast yourself back to the arena if your damage is high enough; or, at the very least, you can damage yourself and be able to use another Up B. However, one must be careful: Snake will miss the explosion if he's fastfalling, and triggering Down Special may accidentally accelerate him.
Sonic
All of Sonic's B-Attacks are recoveries. The Spin Dash and Spin Charge move him forward considerably, and his Homing Attack can be good against edgeguarders and edgehoggers. Also, the Spring Jump has considerable vertical distance, and does not make him helpless (though he cannot use B-Attacks). His Down aerial has slight horizontal range and can be used after Spring Jump, but you can Directional influence farther, and is only helpful if you are close enough to and above the ledge to minimize air vulnerability.
Squirtle
Squirtle can use Withdraw to aid its horizontal recovery.
Toon Link
See Link.
Wario
Wario can use his bike to aid his horizontal recovery somewhat (this is called Bike Jumping). Also, if he uses a fully charged Wario Waft, it rockets him up farther than his actual recovery.
Wolf
Wolf Flash can aid his horizontal recovery since moves him up at roughly 35 degrees. It also has a large sweetspot to grab the edge, and does not sit at the edge finishing the attack, unlike his Up Special
Yoshi
Yoshi's Egg Throw in Brawl can slightly assist his horizontal and/or vertical recovery as a last resort. Also, while not actually gaining distance, his air dodge can be used in combination with his second jump to provide a great span of invulnerability.
Young Link
See Link.
Zelda
Zelda has no advanced recovery techniques. Din's Fire does make her "glide" forward a bit but is not generally helpful for recovery.
Zero Suit Samus
Zero Suit Samus has two tether recoveries (Plasma Whip and Plasma Wire) and can use Flip Jump. Use them according to the situation. Also, to aid her jumps, use Plasma Wire immediately after jumping (thankfully, this does not require nearly as precise timing as the Zap Jump, for instance) and she will fly a good distance higher into the air.