Paternal contributions to epigenetic inheritance are not well understood. Paternal contributions via marked nucleosomes are particularly understudied, in part because sperm in some organisms replace the majority of nucleosome packaging with protamine packaging. Here we report that in Caenorhabditis elegans sperm, the genome is packaged in nucleosomes and carries a histone-based epigenetic memory of genes expressed during spermatogenesis, which unexpectedly include genes well known for their expression during oogenesis. In sperm, genes with spermatogenesis-restricted expression are uniquely marked with both active and repressive marks, which may reflect a sperm-specific chromatin signature. We further demonstrate that epigenetic information provided by sperm is important and in fact sufficient to guide proper germ cell development in offspring. This study establishes one mode of paternal epigenetic inheritance and offers a potential mechanism for how the life experiences of fathers may impact the development and health of their descendants.