In Melee, the only characters that were not popularly requested characters were Ice Climbers, Mr. Game & Watch, Dr. Mario, and Roy. Pichu was among the most popular (probably the most popular overall) Pokemon of Generation 2, while Young Link actually tied with Zelda and Sheik on Sakurai's pre-Melee poll.
In Brawl, the only characters that got in that had few if any requests to them were Snake, Zero Suit Samus, ROB, and to an extent Pokemon Trainer (Ash Ketchum was a popular choice in Sakurai's pre-Melee poll, and there was "some" interest in a trainer in the West, while there has been quite a bit of interest in promoting Charizard and Squirtle to playable status even before Melee was unveiled).
Typically, most of the characters that get into Smash Bros. had a lot of interest by fans to get in the first place. Does that mean popularity is the sole factor for inclusion? No, but it certainly helps you get noticed and is a plus on a resume towards inclusion. Ganondorf and Sonic (and Wolf) were the most wanted characters for their respective Smash Bros. games, yet got in as last minute additions. Wario, Diddy Kong, and King Dedede were also incredibly popular choices for Melee, while Ridley and Isaac were for Brawl, yet they still did not get in.
Though although some popular choices were skipped, lots of others got picked as well. It all depends on Sakurai's priorities. For example, it is rumored Sakurai did not go with Wario for Melee because he had already added two original Mario characters (Bowser and Peach), and he thought Wario deserved better than being a clone when he thought of a Mario series clone slot. King Dedede was planned since Smash 64 (so he obviously thought he was worthy towards inclusion since the very beginning and probably already had ideas on what to do with him then), yet got bumped out of 64 due to time and budget constraints (Smash 64 was a rather shoestring game), and for Melee, he thought the larger actors of Nintendo's larger series (Mario, Zelda, Pokemon) were a higher priority than his own creation (Kirby), of which he wanted to be humble about.
We will learn much, much more about Sakurai's thinking this time around once E3 finally comes along. However, from Sakurai's present statements, he seems to think other focuses aside from beefing up the character and stage count will be needed to keep Smash Bros. fresh, and has talked about the need for more balance. Will this mean we will get less newcomers this time around? Well who knows. Keep in mind that Sakurai also said in 2006 that his team greatly struggled to get to 26 playable characters in Melee, and that it would be very challenging to go over that, and we ended up getting far more newcomers than any previous Smash Bros. game.