Storytelling can be used by conversational agents in a wide variety of domains to maintain user engagement, both within a single interaction and over dozens or hun- dreds of interactions over time. The majority of agents designed with this ability to date deliver their stories as monologues without user input. However, people rarely tell stories in conversations this way, and instead rely on listener contributions to guide the storytelling process. Corpus-based studies of human-human conversational storytelling have demonstrated greater engagement, in the form of longer stories, when listeners co-construct stories this way. We describe a research framework for the generation and evaluation of co-constructed social stories in the context of task-based conversations, and a study on the effects of degree of user-agent story co-construction on user engagement. We find that users are more en- gaged with storytelling agents that allow them to co- construct stories in a contentful manner by asking ques- tions, compared to co-construction through acknowl- edgments only.