I've tried running a mono blue Caldara deck and it was okay, but I thought it would be more interesting to run a dual color deck with her, especially since there is a ton of discard shenanigans in lore. What you want to start with is an Elf-stone and Galdor of the Havens or an Elven-light.
Getting the card draw is important because you need to find Prince Imrahil and discard him or put him into play (or both). Discarding any of the blue allies is a great idea, especially if you are able to Sword-thain a named one. I like to Sword-thain anyone but Prince Imrahil (for obvious reasons) or Galdor of the Havens because of Caldara and her ability.
If Prince Imrahil is in play and a named blue sprit ally has Sword-thain, three spirit allies will be pulled from your discard pile (if you have any) and put into play. It is important to wait and do this at a crucial moment rather than doing it randomly. I find it to be effective in the combat phase when you have need of blockers or attackers to deal with enemies, or if you desperately need more will power in the questing phase.
There are some games where the encounter deck has stymied me and I am only able to pull Prince Imrahil from the discard pile, but this was still effective because he was able to block an incoming attack that any of my heroes would have died from because it would have been unblocked, thus, I was able to retain three heroes. Also, Glorfindel can still be played from the discard even if you are unable to bring him in with Caldara.
This deck has been spotlighted by Cardboard of the Rings: cardboardoftherings.com