A highway is a 2-3 tile wide paved road that leads between two or more deeds. Single paved roads that are paved on the edge with gravel also count as a highway.
Official protected highways use a marker per tile corner which will protect all 4 tiles around it. Most of these markers are called Catseyes, with a second type called a Waystone, which is used primarily at junctions, e.g. where roads meet or as a terminus (on deed).
More information on the mechanics on highways can be found on this Google document.