The present research is concerned with developing analysis methods for analyzing and exploring finite-amplitude elastic wave propagation through periodic media. Periodic arrangements of materials with high acoustic impedance contrasts can be employed to control wave propagation. These systems are often termed phononic crystals or metamaterials, depending on the specific design and purpose. Design of these systems usually relies on computation and analysis of dispersion band structures which contain information about wave propagation speed and direction. The location and influence of complete (and partial) band gaps is a particularly interesting characteristic. Wave propagation is prohibited for frequencies that correspond to band gaps; thus, periodic systems behave as filters, wave guides, and lenses at certain frequencies. Controlling these behaviors has typically been limited to the manufacturing stage or the application of external stimuli to distort material configurations. The inclusion of nonlinear elements in periodic unit cells offers an option for passive tuning of the dispersion band structure through amplitude-dependence. Hence, dispersion analysis methods which may be utilized in the design of nonlinear phononic crystals and metamaterials are required. The approach taken herein utilizes Bloch wave-based perturbation analysis methods for obtaining closed-form expressions for dispersion amplitude-dependence. The influence of material and geometric nonlinearities on the dispersion relationship is investigated. It is shown that dispersion shifts result from both self-action (monochromatic excitation) and wave-interaction (multi-frequency excitation), the latter enabling dynamic anisotropy in periodic media. A particularly novel aspect of this work is the ease with which band structures of discretized systems may be analyzed. This connection enables topology optimization of unit cells with nonlinear elements. Several important periodic systems are considered including monoatomic lattices, multilayer materials, and plane stress matrix-inclusion configurations. The analysis methods are further developed into a procedure which can be implemented numerically with existing finite-element analysis software for analyzing geometrically-complex materials.