How can the number of genes increase through evolution?
Mutations can have all sorts of impacts on genetic architecture. A mutation can have a small impact on a genetic architecture such as 


Substitution
Insertion
Deletion


or can have a much bigger impact on a genetic architecture such as 


Amplification (incl. gene duplication)
Deletions
Chromosomal translocations
Interstitial deletions
Chromosomal inversions
Chromosome duplication
Change in ploidy number


Some of these mutations (gene duplication, Chromosome duplication, change in ploidy number) typically allows duplicating DNA segments. After duplication, the two copies of a gene can diverge through neofunctionalization or subfunctionalization. Have a look at wikipedia > gene duplication to understand what biochemical processes can cause such mutations (e.g. ectopic recombination, retrotransposition event, replication slippage).


  Am I correct in thinking that creatures within the same species who mutate to have an additional gene in their genome would normally be infertile?


You are being mistaken. I understand the naive intuition that a change in copy number of a given gene would be extremely deleterious but in reality, living organisms seem much more resilient to such Copy-Number Variation (CNV) than you would think. Of course, some CNV are associated with diseases but it is not the case of all (McCarroll and Altshuler 2007).

Gene duplications are actually quite common whether in C. elegans (Lipinski et al. 2011) or in humans (Cotton and Page 2005). Chromosomal duplications are also common (Bowers et al. 2002). Even whole-genome duplications (see a classical example in Wolfe 2015) have played major roles in the evolution of many lineages (Whitton and Otto 2010) including vertebrates (Dehal and Boore 2005).

Below is a phylogenetic tree of sequenced green plant genomes highlighting some of the main events of whole-genome duplication.



For the record, some species of strawberries are decaploid (10 copies) (Hummer 2012). Then there are the extremes. In Entamoeba populations, there can be variation in ploidy level among individuals ranging from diploid (2 copies) to tetracontaploid (40 copies) (Mukherjee et al. 2008)!