Research has shown that human-agent relationships form in similar ways to human-human relationships. Since children do not have the same critical analysis skills as adults (and may over-trust technology, for example), this relationship-formation is concerning. Nonetheless, little research investigates children's perceptions of conversational agents in-depth, and even less investigates how education might change these perceptions. We present K-12 workshops with associated conversational AI concepts to encourage healthier understanding and relationships with agents. Through studies with the curriculum, and children and parents from various countries, we found participants' perceptions of agents -- specifically their partner models and trust -- changed. When participants discussed changes in trust of agents, we found they most often mentioned learning something. For example, they frequently mentioned learning where agents obtained information, what agents do with this information and how agents are programmed. Based on the results, we developed recommendations for teaching conversational agent concepts, including emphasizing the concepts students found most challenging, like training, turn-taking and terminology; supplementing agent development activities with related learning activities; fostering appropriate levels of trust towards agents; and fostering accurate partner models of agents. Through such pedagogy, students can learn to better understand conversational AI and what it means to have it in the world.