Navigation systems capable of estimating the six-degrees-of-freedom (d.o.f.) position and orientation (pose) of an object while in motion have been actively developed within the research community for several decades. Numerous potential applications include human-navigation aids for the visually impaired, first responders, and firefighters, as well as localization systems for autonomous vehicles such as submarines, ground robots, unmanned aerial vehicles, and spacecraft. The mobile industry has also recently become interested in six-dof localization for enabling interesting new applications on smart phones and tablets, such as games that are aware of motions in 3D space. The Global Positioning System (GPS) satellite network has been relied on extensively in pose-estimation applications; however, both humans and vehicles often need to operate in a wide variety of environments that preclude the use of GPS (e.g., underwater, inside buildings, in the urban canyon, and on other planets). In order to estimate the 3D motion of person or robot in GPS-denied areas, it is requisite to employ sensors to determine the platform's displacement over time. To this end, inertial measurement units (IMUs) that sense the three-d.o.f rotational velocity as well as three-d.o.f. linear acceleration have been extensively used. IMU measurements, however, are corrupted by both sensor noise and bias, causing the resulting pose estimates to quickly become unreliable for navigation purposes. Although high-accuracy IMUs exist, they remain prohibitively expensive for widespread use. For this reason, it is common to aid an inertial navigation system (INS) with an alternative sensor such as a laser scanner, sonar, radar, or camera whose measurements can be employed to determine the platform's pose (or motion) with respect to the surrounding environment. Of these possible aiding sources, cameras have received significant attention due to their small size and weight, and the rich information that they supply. State-of-the-art vision-aided inertial navigation systems (VINS) are able to provide highly-accurate pose estimates over short periods of time, however, they continue to exhibit limitations that prevent them from being used in critical applications for long-term deployment. Most notably, current approaches produce inconsistent state estimates, i.e., the errors are biased and the corresponding uncertainty in the estimate is unduely small. In this thesis, we examine two key sources of estimator inconsistency for VINS, and propose solutions to mitigate these issues.