Inertial navigation systems suffer from drift errors that degrade their performance. The main existing techniques to mitigate such impairment are based on the detection of stance phases under the specific situational context of pedestrian walking with a foot-mounted inertial measurement unit (IMU). Existing approaches achieve acceptable performances only under simple circumstances, such as smooth movements and short periods of time. In addition, they lack a principled unifying methodology to exploit contextual information. In this paper, we establish a general framework for context-aided inertial navigation and present efficient algorithms for its implementation based on the inference technique called belief condensation (BC). We evaluate the proposed techniques against the state of the art through the experimental case study of pedestrian walking with a foot-mounted IMU. Our results show that the proposed techniques can remarkably improve the navigation accuracy while keeping moderate complexities.