You find books about Shar and Selune throughout the game, but they are easy to miss, I guess. I never thought, how it would be for new players, but since you mentioned it and Shar is heavily featured in the game, they maybe should invest in a scene explaining her a bit more for new players. It's not like Abdirak and his goddess Loviatar - I'm pretty sure you can go through the game without indepth knowledge of Loviatar, but it's different with Shar - and probably Selune, who is also heavily featured. You can ask Shadowheart about Shar worshipping later, but that is after you have to react to her being a cleric of that goddess.
The point is PLAYER KNOWLEDGE VS. CHARACTER KNOWLEDGE.
When you find a big kettle of crazy, it's best not to stir it. --Dilbert cartoon
"Interplay.some zombiefied unlife thing going on there" - skavenhorde at RPGWatch