They get built on property usually owned and leased by the city/state. The city/state usually owns a about a square mile around each highway mile so they own the land of the side of the highway and let companies build billboards and rent out the land space. That money is supposed to go to highway upkeep, but that’s in a perfect world so who knows where it’s going.