On top of what Derf already said, the key to this match up is proactive denial of short hops. Since Falcon can so quickly cover horizontal air space, it's near impossible to challenge any of his aerials on reaction, and like Derf said, most (if not all) of his aerials are safe of IC's shield. Whether they have a positive frame advantage or capitalize on the fact that ICs lack an OoS shield game, Falcon has little worries about advancing or pressuring a grounded ICs. Having a strong yomi game is critical in this match up, but thankfully most Falcon's short hop all the time, taking a large chunk of the guessing game out of the picture. Some options that I personally like to use (other than the one's that Derf suggested) include:
WD in Up-Smash (sometimes in place, as the large hitbox can work as a good anti-air too. If used in place, make sure you are synced, as the extra up-smash from Nana greatly helps with the timing.) This move is excellent for catching a short-hop happy Falcon, but it should also go without saying that if used improperly or excessively can result in a costly punish. Key times to use this move are when you are within the range from directly next to a short hopping Falcon to about the midpoint of his furthest short hop distance. If you are near then end of his furthest horizontal short hop distance, I would recommend wavedashing just outside of his horizontal range and using a up angled f-tilt like Derf said. (P.S. Fly makes good use of this technique throughout the match, so if you want more examples, just watch the rest of the set.)
Rising Nair. [edit: I think I grabbed the wrong part of the vid by a few seconds. Just wait until he loses Nana and b-throws Falcon off stage; the example follows shortly afterwards.] This is about as close as it gets to a reactionary punish, but is very difficult to space properly. The idea is to catch Falcon short hopping towards you with a vertically inclined aerial by low-profiling underneath him and using the topmost hitbox to intercept him. I'd recommend this for a more agro style of ICs, but this technique becomes even more difficult when Nana is around, since she occupies additional space around Falcon, making her an easy target.
If you begin to shut down Falcon's short hops, he might be tempted to approach higher by using full hops or double jumps. If that's the case, then you can now punish on reaction with
up-airs by abusing the fact that the
Ice Climbers have a shorter full hop than Falcon, almost leaving them just far enough below him to reach with a well spaced up-air. (Notice how S2J double jumped several times in front of Fly; this might have been a giveaway that he should punish with an up-air).
The way I approach this match up is like trying to control a fire; you have to remain just outside of the range where you can get burned in order to prevent it from getting out. The match up is very difficult because the IC's don't have a lot of safe options to punish a Falcon while the opposite is true for Falcon. I think it's also worth noting that Falcon is probably my worst match-up, but mostly because I think I play too passively against him. Most of my good plays against Falcons have come from not allowing them to start their aerial pressure, so don't be afraid to make a few gutsy reads to discourage them from abusing the air space that ICs have a hard time occupying.
P.S. Please don't down smash too often in this match up; Falcon's love it when you do that.