Zelda is so easy to beat.
I've been playing a great pro Zelda since melee. Coming to Brawl I see a lot of people getting schooled by Zelda, which I find to be pretty funny. Given that she's changed so little, I know perfectly how to deal with her already. I shall impart this wisdom.
Airdodge/spotdodge. Learn to use these well, and most Zeldas will already be defeated. If you're in the air and she Din's Fire spams, don't drift towards her, but rather straight down. Don't roll, that gives her a chance to set you up. Proceed at a cautious pace, tossing projectiles when you feel like it. Always try to get Zelda to make the first move, if you can't, then use one of your character's priority moves to open the combo.
Specific character strategies? Go for speed. Speed is her weakness. She can be combo'd to death by pretty much anyone fast enough.
If you have to use a slow character, focus on only getting in a hit when she's not going to get the chance to kick or upsmash. Naryu's Love is pathetic. There is a tiny window where she can be hit, some lagtime after the move. It was larger in Melee than it is now in Brawl, but still there, still exploitable.
Dodging Farore's Wind is pretty simple too, though only the good Zelda will aim to hit you with it on their descent. If you learn where she lands(always in a straight line), it can be avoided. However for you Zelda players who don't currently try this, do. Even a character that can predict it, will have to spotdodge or roll away, more oftenly roll.
For more pro-Zelda advice.. Forward Smash when they're coming at you from the front, but your upsmash won't connect. You may choose to forward smash instead of grab, for setups, unless you're in danger of diminishing returns. This IS a great setup, as people will clamber to the ground, and you can chase for the kick. Always maintain a safe distance between you and the enemy, making sure that you will have a move to counter what they will try to do to you. Forward smashing typically stops dashing, most smash/tilts, and can kill at pretty decent percents. Upsmashing stops almost all dairs and will drag the person into the damage, just like forward smashes. Both of these moves should be used in a shielding, defensive manner, and not in an attacking manner.
On the attack, nair is your friend. Naryu's Love can be useful when you know you'll hit the opponent and knock them away. Not everyone knows where you will end up at the end of Naryu's Love. For your information, they will always go the direction Zelda is facing.
Don't waste your time with downtilts/downsmash. unless you're just desperate or are facing diminishing returns. Maybe it's just bad habit from melee, but it just leaves you too far open and there are better moves to use.
That's as much as I can think of now. Time to go beat the best Zelda there is, some more.