Somehow I'm begun wondering if I'm doing this the right way. The Cure spell instructs you to shuffle your deck. I've been playing it that I retrieve cards from the discard pile, shuffle them into the deck, then recharge or discard the Cure spell, depending on the recharge check result.
Now I've read in some FAQ resolution (I think on Radillo's spell recycling ability) that certain things have to happen immediately of which recharging might posible be one. So I might have to attempt the recharge immediatly on playing the spell, resulting in either the spell being recharged before shuffling, and thus shuffled into the deck, or the spell being discarded and possibly retrieved from the discard pile and shuffled into the deck.
I admit I'm confused now, what is the correct way to play?
You've been doing it correctly. See this FAQ for the latest version of the rule about this. The Cure spell is set aside while you resolve the effects from playing it (rolling a d4, getting random cards from your discard pile, and shuffle them into your deck), then you attempt to recharge it.
Thanks Hawkmoon, that is what I assumed, but I wanted to make sure.