I don't bother with regular scouts. They are not very efficient at their job. Too small of sensor radius, too slow, and not enough range, plus they are built upon a such a puny hull.

I suggest you design your own ship, a sensor ship. Start with a cargo hull, and add some sensors, engines, and life support. Smaller maps don't need much, since they are quickly searched, as such you might want to favour life support so you can scan everything with your first ship. Bigger maps can take much longer to scan so you may want to research several levels in sensors, life support, and engines so you may later upgrade/replace your sensor ships when you are able to.

An important thing to note is, a ship may not have a sensor range greater of 15. I heard that having a number larger than this created some problems when the game was first released, including game lag, so thats why there is the limit.

As for search menthods, there are two you should know. The first is to search the immediate area you are likely be dealing with. Things like colonization works better if you know where the best planets are, as do getting galactic resources. Back when I was still new to this game, I saw a constructor belonging to another civ pass by my homeworld, and nab a galactic resource I didn't know about mere parsecs away. The other is to do a thorough search of the whole map (or whatever you can reach). A good place to start is in the corner of the map, and then scan every sector along the edge while you make your way to another corner. Once done, move over a sector or 2 and repeat the process.