A comprehensive matrix of composite poly(ethyleneoxide) (PEO)-based solid-state electrolytes was developed in order to systematically study a number of variables and their impact upon the electrochemical properties of the resulting materials. The different parameters studied in the fabrication of these materials include: (i) the lithium electrolyte salt type, (ii) the ether oxygen to lithium ratio, (iii) the molecular weight of PEO, (iv) the type of ceramic additive used, either aluminum oxide (Al2O3), silicon oxide (SiO2), or titanium oxide (TiO2), (v) the particle size of the additives used, and (vi) the concentration of additive (wt.%). The standard lithium salt used for the preparation of these electrolytes was lithium trifluoromethanesulfonate (lithium triflate or LiSO3CF3), which served as the baseline electrolyte salt. Other lithium salts investigated include: lithium perchlorate (LiClO4) and lithium bis-trifluoromethanesulfonimide (LiN(SO2CF3)2). Conductivity measurements were performed for each electrolyte membrane over a wide temperature range (23–100°C). In addition, cyclic voltammetry measurements were performed on selected PEO membranes as a function of temperature to determine the impact of various parameters upon the electrochemical stability. It was observed that the parameter that displayed the most significant effect upon the PEO-base polymer conductivity was the lithium salt type employed. The lithium triflate salt-containing PEO polymers demonstrated the best mechanical properties before and after heat treatment. Ceramic fillers also appear to enhance the mechanical properties of PEO polymer electrolytes at temperatures above the melting point of PEO (60–70°C). In addition to investigating the electrochemical characteristics of the composite membrane, solid state 7Li NMR characterization was performed to study ionic mobility by measuring spectral line widths and lithium self-diffusion coefficients. It was determined that ceramic nanoparticle additives can enhance the Li+ diffusivity without a corresponding increase in polymer segmental mobility.