You could also have the players find an ancient prayerbook from their church (or an earlier version of their church). In it are older prayers and rituals that have been forgotten over the years, and when the cleric uses them as part of his morning prayer/meditation, the god or goddess in question is pleased and grants access to those new spells. The reason? The deity had been waiting to be properly petitioned for these particular spells.
Or you could have these spells be more associated with certain different orders within the church. For example, Pelor, the sun god in Greyhawk, is associated with healing, light, the sun, travel, strength and destruction of undead. The Order of Pelor-of-the-Balm might be an order dedicated to the healing power of the god, and thusly has access to certain healing spells regular clerics don't. The Order of Pelor the Holy Light might be focused on the sun and undead-killing aspects of the god, and have undead-bane spells. The Order of the Wandering Sun might be those Pelorites who travel as the sun does, and have particular spells of movement and protection. The Order of Pelor the Mighty might be the militant arm of the church, with strength and battle spells the main church doesn't.