Commensal microbial communities have immense effects on their vertebrate hosts, contributing to a number of physiological functions as well as host fitness. In particular, host immunity is strongly linked to microbiota composition through poorly understood bi-directional links. Gene expression may be a potential mediator of these links between microbial communities and host function. However few studies have investigated connections between microbiota composition and expression of host immune genes in complex systems. Here we leverage a large study of laboratory-raised fish from the species Gasterosteus aculeatus (three-spined stickleback) to document correlations between gene expression and microbiome composition. First, we examined correlations between microbiome alpha diversity and gene expression. Our results demonstrate robust positive associations between microbial alpha diversity and expression of host immunity. Next, we examined correlations between host gene expression and abundance of microbial taxa. We identified 15 microbial families that were highly correlated to host gene expression. These families were all tightly correlated to host expression of immune genes and processes, falling into one of three categories: those positively correlated, negatively correlated, and neutrally related to immune processes. Furthermore, we highlight several important immune processes that are commonly associated with abundance of these taxons, including both macrophage and B cell functions. Further functional characterization of microbial taxa will help disentangle the mechanisms of the correlations described here. In sum, our study supports prevailing hypotheses of intimate links between host immunity and gut microbiome composition.