Apple Johnny is the American culture hero Johnny Apple Seed born John Chapman. Legendary in his lifetime, he introduced apple trees to Ohio, Indiana and Illinois. Famously kind to all people and animals, he was also a very conservative figure.
Paul Bunyan is usually depicted as a giant lumberjack with a large ox called Babe as a companion.
He was originally documented in 1910 by journalist James MacGillvray, who used him to advertise a logging company. The modern Paul Bunyan figure is said to be a reworking of older stories, so he is a fakelore (made-up folklore sold as authentic) figure.
Gaiman hints that the woman in the darkened room is a Gorgon from Greek mythology.
She keeps dead mice and crickets in her fridge, presumably to feed to the snakes which form her hair. In legend, if you look on a Gorgon's face you are turned to stone.
These women could be Kitsune.
Kitsune is the Japanese word for fox, but it also refers to fox-spirits; these can take on human form, often as beautiful young women. Some Kitsune are benevolent and others are mischievous. White Kitsune are associated with the Shinto god of fertility, rice and agriculture, Inari.