Prioritize the coast and around your capital. Scout rush targets thoroughly, otherwise you can skip land their likely to settle to look for huts.
So how do you balance that all?
My preferred path is scout along the coast, then hook around my capital in a way that maximizes tiles revealed. Second warrior will scout the other side of the capital.
There's also a difference if you want your scouting unit to live or not. If you don't, just send him down the coastline as far away as possible to contact AI and happen upon huts. Otherwise sweep back and forth in arcs, and get him back to safety in time to fog bust for your settlers.