If I wait long enough, will Katria just mark all of the locations on my map for me(is so, how long do I have to wait?)? I don't feel like searching for all of them.

Check out the map in her Journal.
Compare the marks to the world map.

You -have- to search out the locations...... A nice nod to the older school, where you got just about that; a blurry map. The rest was up to you. Best quest I've played in quite awhile.....

This quest is AWESOME! just check her journal for it

Agreed, I can't stand the auto locate and compass. Old school Morrowind map was the best, you had to listen to quest giver for location markers nothing was marked for you.
Though the current map and quick travel makes it easier for casual gamers to enjoy the adventure.