Una primera versión
La primera versión del origen del nombre de Navalmanzano de la que tenemos constancia es del año 1155. Esta imagen ha sido extraída de la «Documentación medieval de la Catedral de Segovia (1115-1300)«.
En ella se habla de una serna entre Fuentepelayo y Navalmanzano, y se refiere a Navalmanzano como «Nava de Maçanu«.

Otra versión del año 1791
En esta otra imagen, extraída de «Memorias políticas y económicas sobre los frutos, comercio …, Volumen 10», se refieren a nuestro pueblo como «Nava del Manzano«:

Una versión más del año 1832
En esta referencia perdemos «la d» y se hace mención al pueblo de Navalmanzano como «Nava el Manzano«. Acortar este nombre a Navalmanzano ya es solo cuestión de practicidad.
La siguiente imagen la he extraído del «Diccionario Geográfico Universal«, dedicado a la Reina y redactado en 1832 por la sociedad de literatos S.B.M.F.C.L.D.:

La transcripción del texto es la siguiente:
NAVA EL MANZANO , lug. sec. de Esp., prov., obisp. y á 6 leg. de Segovia , part. de Cuellar. A. P. Pobl. 1.5o8 hab. Tiene mediano caserío. Sit. en la carretera que conduce desde Segovia á Valladolid , á 1 1/2 leg. del rio Pirón. Prod. pocos granos y bastante leña; y cria ganado.