The rapid proliferation of edge computing infrastructure has significantly accelerated the adoption of edge-native applications, ranging from autonomous vehicles to augmented reality and real-time analytics. Microservice, renowned for its lightweight, loosely coupled, and modular architecture, has emerged as the de-facto standard for developing edge native applications. However, the resource scarcity and heterogeneity, coupled with request dynamics in edge environments, pose substantial challenges for effective microservice orchestration. To address these challenges, we propose MicroEdge, an online optimization framework designed for cost-efficient microservice orchestration in edge-native environments. MicroEdge employs a multi-level optimization approach by strategically coordinating four key dimensions: microservice placement, layer placement, layer pulling, and user request scheduling. The framework confronts two fundamental challenges in solving this joint optimization problem: (1) the time-coupled nature of long-term holistic cost minimization, and (2) the NP-hardness of the underlying problem. MicroEdge tackles these dual challenges by integrating a regularization method for online algorithm design and a dependent rounding technique for approximation algorithm design. Both rigorous theoretical analysis and extensive simulations driven by realistic Alibaba microservice workload traces validate the efficacy of MicroEdge.