Fantasy is a form of speculative fiction in which physical laws differ from our own through a reason for which no scientific explanation is offered, or which take place a world wholly different from our own.
A critical characteristic is that the world feature some difference from Earth that is not a result of science or technology, but rather the result of magic or other anomalous phenomena.
Comic fantasy is a subgenre of Fantasy that is primarily humorous in intent and tone. Usually set in imaginary worlds, comic fantasy often includes puns on and parodies of other works of fantasy. It is sometimes known as Low Fantasy in contrast to High Fantasy which is primarily serious in intent and tone.
Examples: Slayers, Gokudou-kun Manyuki, Akazukin Chacha, Mahoujin Guru Guru...
Contemporary fantasy is a subgenre of fantasy, also known as contemporary urban fantasy, modern-day fantasy, or indigenous fantasy. These terms are used to describe stories set in the putative real world (often referred to as consensus reality) in contemporary times, in which, it is revealed, magic and magical creatures exist, either living in the interstices of our world or leaking over from alternate worlds. It thus has much in common with, and sometimes overlaps with, secret histories.
Examples: Tactics, Chiccha na Yukitsukai Sugar,...
Dark fantasy in this context refers to stories that focus on elements usually found in the horror genre but which take place in a setting more alike sword and sorcery or high fantasy. Dark fantasy includes "grittier" fantasy, conducted in settings which represent the brutality of the medieval period more truly than the traditionally idealised representations of conventional fantasy, generally with a dash of supernatural horror. It may or may not take place in its own fantasy world.
Examples: Berserk, Vampire Hunter D: Bloodlust,...
According to The Encyclopedia of Fantasy, high fantasy is 'Fantasies set in otherworlds, specifically secondary worlds, and which deal with matters affecting the destiny of these worlds.' Basically a catchall for animes that feature fantastical races (such as elves and dwarves), wizards, and such.
Examples: Lodoss-tou Senki, Final Fantasy Unlimited, Words Worth,...
It has been said before that Genre::Fantasy::Magic is redundant, since fantasy already implies presence of magic. That's true, but it might still be of some use to keep that category, to categorize anime in which magic plays central role -- such as Mahou Tsukai ni Taisetsu na Koto.
Most famously magical-girl stories feature young girls with superhuman abilities who are forced to fight evil and protect the Earth.
See also: Wiki - Mahou shoujo
Examples: Cardcaptor Sakura, Sailor Moon, Magic Knight Rayearth, Pretty Sammy and Futari wa Pretty Cure.