According to a civil engineer (video in Spanish), the Appian way was built as a concession. This is, it was built by a private "company", paid by the state.
Unfortunately, Wikipedia is not clear about who built the Appian way. It only states who "commissioned" it.
More generally, regarding public Roman roads:
Financing road building was a Roman government responsibility. Maintenance, however, was generally left to the province. The officials tasked with fund-raising were the curatores viarum. They had a number of methods available to them. Private citizens with an interest in the road could be asked to contribute to its repair. High officials might distribute largesse to be used for roads. Censors, who were in charge of public morals and public works, were expected to fund repairs suâ pecuniâ (with their own money). Beyond those means, taxes were required.
And:
Roman roads were named after the censor who had ordered their construction or reconstruction.
All this however doesn't state who built the roads.
Any expert on the topic?