A highway is defined as a paved road connecting two or more deeds with a format of either a single tile road with sand borders on each side -or- 2 or more tiles wide.
The sand functions to keep trees from growing directly next to the highway as to increase the visibility against threats. Higher quality highways can be painstakingly terraformed. Some highways can be found to be paved with much more time-intensive stone slabs.
For information on the rulings on highways please see this forum post.