What is the origin of Haibane? Where do the Haibane come from? A cocoon but where does the cocoon choose to appear?
Warning: Major spoilers if you haven't watched Haibane Renmei all the way through.
First off Haibane Renmei leaves much information about the story and setting intentionally vague so any answer to this question is going to be partly opinion based. Most of the other Haibane seem more or less content with their ignorance of things, but Rakka, the audience surrogate, is befuddled and confused as to what exactly the Haibane are and repeatedly questions it throughout the story. Rakka goes out of her way to try to unravel what is going on, checking out books from the library, or teaching herself the Toga/Communicator sign language. The Communicator is so impressed by her inquisitiveness, that he even gives Rakka a job inside the mysterious Wall itself. Like Rakka, the show invites us the viewers to think more deeply about the world it presents so we can piece things together ourselves.
Okay onward to the answer, or at least what I think the answer is....
Despite the wings and halos, the Haibane are not angels. The magical Wall surrounding the town is said more than once to collect and store memories for a time before releasing them. The wall not only collects memories, but also collects the souls of children or teenagers who have died with some aspect of their life unfulfilled. The cocoon's function is to give these souls a new body so they can get a second chance to fix whatever it was they couldn't fix in their previous life before the wall releases them to move on during their "day of flight." We see this process play out with Kuu and later Reki. The Haibane are reincarnated human souls existing in a sort of temporary body that's not quite human but close enough while they try to work out their issues. A cocoon appears whenever the wall captures a young unfulfilled soul and serves the necessary function of growing a body for that soul to inhabit. It's not entirely clear why the cocoons grow in specific locations but all such locations are away from the "normal" humans, within the confines of the wall, and near other Haibane who presumably will know what to do when a cocoon appears and how to best take care of newly born Haibane.
Well I hope that answers your question.