Expanding on the information above, there is also an two part OVA series. It begins with a short recap of the story so far, but knowledge of the tv-series or manga (I'll come to that later) is really required to understand who is who and what their relationships are. The story is set and taken from the middle of the manga and deals with king De Den Den (Number one one the "Stupid Names in Anime" Top Ten list...) who is building a citadel impervious to Folm-Magic, at the cost of his citizens, who are starving and the fairy folk, whom he enslaved to work for him. Maze, Mil and her friends come into the kingdom, and after quite a bit of hilarious exploits (most memorable: The Dungeon of Death and the Quiz Show) and with the help of the Kings offspring, Princess Mix and Prince Nuts (their names would rank way up there, too!) manage to convince King De Den Den back to good.
The content is a bit more mature than the tv-series, with more fan service and sexual encounters (although one does not see the act itself).
Now, onward to the manga: Originally, the TV and OAV series are both based on a 6 volume manga series published by Kadokawa Comics and written and drawn by by Omishi Rei and Akahori Satoru. As the series has been adapted from the manga, it features the same character design and largely the same story.
Finally, going all the way back to the roots, to the original basis of the series, there was a japanese paperback novel series that started in 1993, of which I own the first two volumes. As I have not read them yet, not seen any others, I don't know if there is more than those two books.
Ukyuuuuu!