I'm aware that when you have "then" in the rules text of a card, you have to successfully perform the stuff before the "then" to do the stuff after it. But my question is, how much of it? Valorous Mage states "Action: when this unit enters play, search the top 5 cards of your deck for a spell card, reveal it, and put it into your hand. Then, shuffle your deck."

If I took the action but did not find a spell card to put into my hand, would I not be able to shuffle my deck?

You do as much of an effect as you can. If you don't find a Spell card to put into your hand, you still shuffle your deck.

What you can't do is pass on searching the top 5 cards and just shuffle the deck.

This is excellent news! I'm gunna try a Gifts of Aenerion/Comet of Cassendora Cataclysm deck and I think the Valorous Mage is going to help. Also Mallumo, you win the prize for shortest turnaround time on a rules question ever. Thanks!