Baba Yaga is a character from Slavic mythology. Portrayed as an old woman, stick thin and with an abnormally long nose, Baba Yaga lives in the forest in a cabin with chicken legs. As if this were not enough to discourage intruders, the cabin also features eyes as windows, sharp teeth in the keyhole in the front door, and on occasion a fence made of human bones with skulls on top. The cabin is very small - Baba Yaga barely fits inside, and according to one account has her legs in one corner, head in another and her nose growing into the ceiling. However, in the story of Vasilia (also sometimes called Vasilissa), the house is at least large enough on the inside to house Vasilia, Baba Yaga, an oven, bed, substantial quantities of food and a cellar.

Baba Yaga is accompanied by a number of supernatural beings, including white, red and black horsemen, who are referred to as "My Bright Dawn, my Red Sun and my Dark Midnight". Baba Yaga also has three menacing disembodied hands, which appear out of nowhere and are at her beck and call. They are referred to as her "Soul Friends" or "Friends of my bosom."

Although the hut can and does move, Baba Yagas preferred means of transportation is a mortar, in which she sits, with her knees reaching her chin, while she pushes herself along with the pestle, using a silver birch broom to clean her tracks behind her. She can also fly with this. Upon finding her cabin in the woods, a magic incantation must be uttered to make it turn around and face one. The incantation reads "Little house, turn thy back to the forest and face me!" An interesting note is that in the adventure game Heroes Quest (later renamed to Quest for Glory), Baba Yaga and her hut feature, with Baba Yaga as an evil witch. To get inside the hut, the hero must fetch a glowing gem for the skull on the gate, which is a direct tie to the legend of Vasilia. However, the problem in getting into the hut does not lie with the making the hut turn around, it is in getting the hut to sit down. The rhyme "Spoiler - hold mouse over to read" is required.

The chicken legged hut does seem to have some basis in fact - the hunter-nomadic people of Uralic and Tungusic descent used to build huts on the stumps of two or three grown trees, about 8 to 10 feet off the ground. The entrance was through a trapdoor in the bottom of the hut. This was done to deter bears, who are smart and strong enough to get into almost any other type of construction, but are unable to climb a rope or ladder to a trapdoor. This allows us to place roughly the date of origin of the Baba Yaga legend - about the time of the Slavic incursion into the land of the Uralic people.

However, although Baba Yaga is even today portrayed as an evil witch, this was not always the case. Baba Yaga quite possibly originated as a representation of nature, and was certainly at one point hailed as the Keeper of the Waters of Life and Death, which could revive the dead or kill, respectively. Upon the dead she would normally drop a little of both, allowing the body to rest and the soul to be reborn. Shinma refers to her as a Bone Mother, guarding the balance between life and death - possibly the Slavic version of the Kindly Ones. Certainly it is not unknown for Baba Yaga to appear as a beautiful woman, although legends appear to have changed her in much the same way as they did Arete. Baba Yaga is used as a threat for naughty children - "Be quiet or Baba Yaga will eat you!" The story of Vasilia has changed Baba Yaga, but the story of Vasilia has changed slightly to accommodate this - where Vasilia was apparently originally released with Baba Yagas blessing for a job well done, in the newer versions (which are still very old) she barely escapes, thanks to her mothers blessing on her head, which Baba Yaga appears unable to stand.

The modern day Baba Yaga is still steeped in tradition (as opposed to the modernisation of vampires), and features strongly in Russian films, cartoons and books. An Italian film called "Baba Yaga" was filmed in 1973, and a musical "Baba Yaga" was released in 1999. In western literature Baba Yaga has appeared in books by Neil Gaiman and Orson Scott Card, amongst others.

Sources:
http://www.everything2.org/index.pl?node=Baba%20Yaga&lastnode_id=174836 (Thanks to ephealy and Shinma)
http://en.wikipedia.org/wiki/Baba_Yaga
http://www.surlalunefairytales.com/babayaga/index.html
http://www.oldrussia.net/baba.html
http://www.mythinglinks.org/BabaYaga.html
http://hazel.forest.net/whootie/stories/baba_yaga_russia.html
http://www.pantheon.org/articles/b/baba_yaga.html
My own recollections playing Heroes Quest and reading The Books of Magic by Neil Gaiman.

JudyT Says that a famous instance of Baba Yaga can be found at Pictures at an Exhibition
Thanks to althorrat for correcting the rhyme from Heroes Quest, and for pointing out that she does make a brief appearance in her mortar in Quest for Glory 4.
Timeshredder pointed out that positive stories about Baba Yaga appeared in the American children's magazine, Jack and Jill, each October.