So, Article VI, Clause 2 of the U.S. Constitution says
This Constitution, and the Laws of the United States which shall be made in Pursuance thereof; and all Treaties made, or which shall be made, under the Authority of the United States, shall be the supreme Law of the Land; and the Judges in every State shall be bound thereby, any Thing in the Constitution or Laws of any State to the Contrary notwithstanding.
However, the Tenth Amendment of the Constitution says
The powers not delegated to the United States by the Constitution, nor prohibited by it to the States, are reserved to the States respectively, or to the people.
Between these two statements it can be hard to determine when the federal government takes precedence over the state governments. What you need to look at is the Enumerated Powers Clause from Article I, Section 8 of the Constitution which gives the Congress the power, among other things
To regulate Commerce with foreign Nations, and among the several States (emphasis mine), and with the Indian Tribes;
This is what allows the Congress to create legislation that orders the States to provide for some of the roads that the federal government builds, because it affects interstate commerce.
It should also be noted that another official name for the Act is the National Interstate and Defense Highways Act. Part of the reasoning for the law was to provide for quick movement between Air Force bases during war, as well as an efficient method of evacuating cities in the event of a nuclear attack. You can read more about the Act at
The Interstate Highway System
Federal Aid Highway Act of 1956