This paper introduces Searching for Us, a tangible pervasive narrative experience that explores collaborative storytelling dynamics through marionette-like avatars, developed through a Research through Design approach. Pairs of users navigate an urban environment, embodying the characters of Hachi, a stray dog, and Buro, his human companion. The system seamlessly integrates real-time environmental data, geolocation, and user interactions to dynamically adapt the narrative. The technical framework of this experience combines physical props, gesture-recognizing avatars, and a responsive computational system, working together to interpret user actions and environmental contexts, translating them into meaningful narrative elements. The narrative structure balances linear progression with user agency, allowing a personalized yet coherent storytelling experience that responds to the immediate physical context. Searching for Us emphasizes embodied presence, co-performance, and shared narrative responsibility by blending physical interaction with digital storytelling. This work contributes to the field of interactive storytelling by demonstrating how tangible interfaces and mixed-reality environments can create compelling narrative experiences.