Once you have chosen a sphere and are past level 10, you can type who sphere and see everybody who has the same sphere as you (except for sphere deception I'm told).

If one of those people in your sphere is an empowered character (healer, druid, shaman, paladin) you can assume that they, to one degree another, are a mortal voice of your god and a.) probably know the shrine location you seek and b.) actually might have a reason to guide you. However, they will be the least likely to come out and give you exact directions - instead they'll probably give you some clues/direction to get you close to looking in the right area. So asking them would certainly be appropriate. Like you said do it IC, have a reason to be approaching them, and do so respectfully.

Another way to get to a shrine is to find an appropriate spot to commune with the god you are seeking and ask for guidance in finding his shrine. Your guild and market square in Galadon are infamously bad places, a battlefield or standing over a recent corpse might be a good place to pray to a war god for example. If the god doesn't rule over your sphere, you should have a reason to be seeking him out in your role. Again, the imm may send some information your way to get you started on your pilgrimmage, you won't be given exact directions.