(in order of appearance)
Chaerephon was Socrates' oldest and closest friend, and shows up several times in Plato's dialogues. He was also mocked along with Socrates in Aristophanes's The Clouds.
Chaerephon and Socrates are apparently on the seashore near Phaleron. Chaerephon opens the dialogue by remarking on a sweet sound he heard coming from the sea, and wonders what it could be. Socrates replies by saying it is a sea-bird called the halcyon, and tells its myth.
Once there was a woman, Halcyon, the daughter of Aeolus, whose husband Ceyx died. Ceyx was extraordinarily handsome, being the son of Eosphorus, the Morning Star. Aching and lamenting the loss of her husband, she searched for him. Being unable to find him on land, she grew wings and now flies around the sea searching for him. Because of her love of her husband, the gods gave her a special privilege: her nesting days in winter are the halcyon days of tranquil weather.
Chaerephon remarks that it seems absurd to believe in ancient stories about birds turning into women or women turning into birds. Socrates takes a more agnostic stance. After explaining his position, Socrates engages in an apostrophe to the halcyon, saying that he will pass on the myth to his children and shall recommend Halcyon's piety and devotion to his two wives, Xanthippe and Myrto. He asks Chaerephon if he'll do the same, and Chaerephon remarks that it would be appropriate. Then they make plans to return to Athens.
* Phaleron was where the old sea-docks of Athens were located, before Themistocles did the work of converting the Piraeus to that task. It's about 3 miles (about 5 kilometers) from Athens.
* The Halcyon myth is a well attested myth. It is also mentioned in the Bibliotheca attributed to Apollodorus, one of the most important sources preserving ancient Greek myths, and in a lovely rendition in Ovid's Metamorphoses, and in Hyginus's Fabulae. Very noticeably, however, the dialogue makes the Ceyx of the story Ceyx of Trachis, who doesn't seem to be the same as the Ceyx in some other sources, although this might just be the usual difficulty of knowing whether the same name in myths are the same person or just two people with the same name.
* Xanthippe is known to have been Socrates's wife; she is portrayed as such by both Plato and Xenophon. Later stories portrayed her as a shrewish woman, so the author is having a bit of fun, having Socrates promise to sing the story of the faithful wife to Xanthippe. Later authors, such as Diogenes Laertius and Plutarch, refer to stories about Socrates taking care of a woman named Myrto; the source was apparently a work attributed to Aristotle (Diogenes Laertius attributes the claim to Aristotle and Plutarch claims it comes from a work called On Good Birth and doubts whether it's really Aristotle's). While Plutarch does not describe her as a wife, Diogenes Laertius does, making Socrates out to be a bigamist.
Socrates responds to Chaerephon's remark about the difficulty of believing the ancient myths by saying that human minds do not seem to be good judges of what is possible:
Many things which are feasible seem, to us, not feasible, and many things which are attainable seem unattainable -- often because of our inexperience, and often because of the childish folly in our minds. For in fact all human beings, even very old men, really do seem to be as foolish as children, since the span of our lives is small indeed, no longer than childhood when compared with all eternity.
Nature/divinity/heaven/cosmos can do extraordinary things beyond our capacity even to express very well. And even in the human case, we see that adults have extraordinary abilities compared to children, and people who are skilled can do things impossible to those who are not. So it appears that we have no way to deny that such things are actually possible to God/nature/the universe (the dialogue uses such terms interchangeably).
The dialogue therefore considers the difficulty of determining what is genuinely impossible. It can also be seen as suggesting, indirectly, that the primary reason for passing on stories like the myth of Halcyon is the moral edification received from them -- in this case, encouragement to strong marital bond. (This does fit with Plato's attitude to myths elsewhere.)
Quotation from Brad Inwood's translation in Plato, Complete Works, Cooper & Hutchinson, eds., 1714-1717.