The characterization of properties of a celestial body (e.g., the gravity field, rotational motion, and 3D shape) is often coupled to some extent with the navigation of an orbiting spacecraft. This task belongs to a class of estimation problem defined in this work as simultaneous navigation and characterization (SNAC). Currently, SNAC is completed almost exclusively offline and on the ground for missions in Earth orbit and deep space. However, autonomous SNAC can reduce mission costs and the burden on ground-based resources. This work enables autonomous SNAC through the development of new algorithms that are robust enough to operate dependably without significant human oversight and that are computationally efficient enough for onboard execution. First, new algorithms are presented to increase the robustness of spacecraft navigation to dynamics modeling deficiencies and system nonlinearities in a computationally efficient manner. Then a novel approach is described for 3D shape reconstruction of celestial bodies using spherical harmonics. Regularization based on empirical knowledge of the shape characteristics of celestial bodies is used to significantly increase the accuracy and robustness of the reconstructed shape. These contributions are leveraged in the development of a new multi-spacecraft mission concept that uses intersatellite radio-frequency measurements and optical landmark tracking to autonomously characterize an asteroid including its gravity field, 3D shape, and rotational motion. This mission concept is called Autonomous Nanosatellite Swarming (ANS). A high-fidelity numerical simulation of three spacecraft orbiting the asteroid 433 Eros demonstrates that ANS provides accurate navigation and asteroid characterization without any a priori shape model. After just 10 orbits, the spacecraft position uncertainty is less than 10m, and the asteroid shape is reconstructed with a root mean square error that is 3.7% of the true average asteroid radius. Additionally, the asteroid gravity spherical harmonic coefficients are estimated to an uncertainty approximately equal to or less than the magnitude of the true coefficients up through degree and order six. From the shape and gravity recovery, the bulk density is estimated with an error that is 0.16% of the true value.