One-tile wide roads are usually sufficient. For heavily used [[highway]]s wider designs have been used, for instance to make it easier to guide your horse or cart on auto-run.
As for paving material, [[gravel]] roads are easiest to make, because they only require one [[rock shard]] per tile to pave. However, they are slower to travel than [[cobblestone]], [[stone slabs]], [[marble slabs]] or [[stone slate slabs]].
Cobblestone and stone slabs are equally fast, up to 17.31 km/h walking speed. But [[stone brick]]s for cobblestone take much less raw material and effort to create than slabs.