Fringe refers to something on the edge or margins. For example a decorative border on a rug, usually loose strands or tassels, could be called a fringe.
In this context (Edinburgh festival) it means to be on the edge culturally. Fringe theater will include more experimental kinds of works. Fringe comedy may include acts that push the limits of humor, of social conventions, etc. So it refers to things that are deliberately odd or weird, but not in a negative way.
Fringe festivals can range from the really outrageous to the mildly unusual. Sometimes things hat were once common might now be considered "fringe", and sometimes acts that are more mainstream in one culture would be fringe in another.