Integrating the unmanned aerial vehicles (UAVs) into the cellular network is envisioned to be a promising technology to significantly enhance the communication performance of both UAVs and existing terrestrial users. In this paper, we first provide an overview on the two main paradigms in cellular UAV communications, i.e., cellular-enabled UAV communication with UAVs as new aerial users served by the ground base stations (GBSs), and UAV-assisted cellular communication with UAVs as new aerial communication platforms serving the terrestrial users. Then, we focus on the former paradigm and study a new UAV trajectory design problem subject to practical communication connectivity constraints with the GBSs. Specifically, we consider a cellular-connected UAV in the mission of flying from an initial location to a final location, during which it needs to maintain reliable communication with the cellular network by associating with one GBS at each time instant. We aim to minimize the UAVs mission completion time by optimizing its trajectory, subject to a quality-of-connectivity constraint of the GBS-UAV link specified by a minimum receive signal-to-noise ratio target. To tackle this challenging non-convex problem, we first propose a graph connectivity based method to verify its feasibility. Next, by examining the GBS-UAV association sequence over time, we obtain useful structural results on the optimal UAV trajectory, based on which two efficient methods are proposed to find high-quality approximate trajectory solutions by leveraging graph theory and convex optimization techniques. The proposed methods are analytically shown to be capable of achieving a flexible trade-off between complexity and performance, and yielding a solution that is arbitrarily close to the optimal solution in polynomial time. Finally, we make concluding remarks and point out some promising directions for future work.