söker is mostly used with abstract objects, if you use it with concrete things it sounds more formal
letar works for both and sounds less formal with abstract things.
söker can also mean 'applies' about jobs.
So if you are asking for directions to a city, söker or letar efter me more correct? As in would you say "Vi letar/söker efter vägen till centrum"
I don't know much of anything about it, so don't take my word for it; But I think that "leta" might be used when one is searching for an object. " Han letar efter nya offer."
I think that "söka" can be used when one is searching for something inevitable. "De sökar efter lycka."
I've heard that they're mostly interchangable, like english "look" and "search"