This paper studies the stability of Kalman filtering over a network subject to random packet losses, which are modeled by a time-homogeneous ergodic Markov process. For second-order systems, necessary and sufficient conditions for stability of the mean estimation error covariance matrices are derived by taking into account the system structure. While for certain classes of higher-order systems, necessary and sufficient conditions are also provided to ensure stability of the mean estimation error covariance matrices. All stability criteria are expressed by simple inequalities in terms of the largest eigenvalue of the open loop matrix and transition probabilities of the Markov process. Their implications and relationships with related results in the literature are discussed.