My take on the fairy tale feel:
1. Assume human-level (or higher) intelligence and ability to act for everything from animals to objects to forces of nature, but don't assume human-like behaviour or reasons to act.
In many fairy tales animals, objects and even fundamental forces of the world (time, the west wind, the sun) can and will speak to anyone willing to talk to them. They are generally on the same level of intelligence as humans, in some cases clearly above. Yet in most cases they are still "true to their nature" so to speak ... so you shouldn't assume humanlike beahviour or even reasons for their doing that would make sense to a normal human.
The west wind may speak to you and treat you like a friend, but in the end its only interest is blowing across the world, uprooting trees and destroying houses. The hedgehogs in the forrest will give you information, but in the end they are hedgehogs and know nothing of the bigger world.
2. One of the core foundations of the world is the "Trade".
Everything is tradable ... everything. You can give your eyesight for 10 years of life, your laughter for the ability to see ghosts or your heart for a potion of invisibility. If you find the right being you can trade nearly everything for everything else. The price is seldom gold or stuff humans would recognize as valuable ... but rather abstract concepts, abilties, body parts or parts of the self.
In such trades your word is binding ... breaking it can have dire consequences, even when no one shpuld be able to know you broke your word ... the world knows ... always.
There are beings who are bound by ancient laws to take certain trades ... the bridge troll must let anyone pass who pays its price.
3. Another core foundation is the "Name" of things.
Words have power, names even more so. Everything has a name and one who knows somethings name has power over it. Dragons must grant you one wish if you speak their true name or they may never harm you. Ghost can be banished by their name and event the stones may follow your command if you speak their names. Your own name holds power also, so you better protect it.
4. There is seldom direct danger, but always a looming threat.
In most fairy tales there is no direct danger or rather there is danger but it is seldom of the hurt, blood & broken bones kind. Children or protagonists may get hurt but that is always minor stuff. What is always there is a looming threat of some kind. The witch may bake the children, the wolf may eat the girl, the hero may get lost in the woods or turned into a frog.
So instead of concentrating on the fights and direct danger, concentrate on fleshing out the threat in the background. That doesn't mean there shouldn't be fights, but it should always be clear, that the big threat is still there.
5. Everything and everyone is always polite and follows the rules of etiquette ... at first.
This ties into point 1, point 2 and even point 3 a bit. If everything is intelligent, there are rules for trading everything and names and words carry power ... then it is better to tread carefully around new acquaintances. Who knows what they can do, who knows what they know? Maybe the wanderer is an old god? Maybe these children know someancient secret?
So everyone will try to gauge the threat level and knowledge of new beings they meet, acting unfailingly polite the whole time. Only when they know enough to act or have no other way will the mask drop and the claws come out.
6. Innocence is one of the most powerful forces.
In many fables and fairy tales the hero is either innocent or at least naive in a charming way. Trough this innocence the heroes are able to overcome the challenges of the story and emerge victorious. Most of the time they change the world for the better this way and achieve wealth, honor, fame or love. Think about the boy in "The Emperor's new clothes" who is the only one not corrupted by power or paralyzed by fear.
Placing something innocent in your story will greatly enhance the fairy tale vibe.
7. There is a narrative structure to the world
This is a bit elusive but it basically boils down to this: The game world itself wants to tell a good story.
So you cannot defeat the ogre in combat but you can banish him because he is afraid of mice (thanks Gus
Like two orcs wrote, fairy tales contain basic wisdom on how to act or how to treat the unknown. They are warnings and manuals how to act when in danger, what to do and what not to do.
So you can assume, that your game world itself wants to tell a good story. Hidden clues, missing scales on dragons backs, random strangers you were kind to becoming important later on.
Like Beoric wrote, Fairy tales follow their own logic ... it's just not the logic of science but the logic of emotion and storytelling.
8. Use Archetypes and cultural images
This ties into point 7. Every culture has recurring images and archetypes in their history. The noble knight, the thief with a heart of gold, the clever old woman ... smarts beat brawn, love cancels hate, innocence conquers cynicism (see point 6).
What may seem trite and simple, even cliche in normal settings and stories can greatly enhance the feel of a fairy tale adventure.
These are my core points I try to keep in mind when I DM a fairy tale adventure.