Federal and State Roles
Tribal compacts with states must be approved by the tribe, the state government and the U.S. Congress, in accordance with each body's internal procedures.
The United States Constitution provides at Article I, Section 8, Clause 3 that Congress has the power:
To regulate Commerce with foreign Nations, and among the several
States, and with the Indian Tribes;
Only "compacts" approved by Congress and not "treaties" between Indian tribes and states are allowed because Article I, Section 10, Clause 1 of the U.S. Constitution states that:
No State shall enter into any Treaty, Alliance, or Confederation; grant Letters of Marque and Reprisal; coin Money; emit Bills of
Credit; make any Thing but gold and silver Coin a Tender in Payment of
Debts; pass any Bill of Attainder, ex post facto Law, or Law impairing
the Obligation of Contracts, or grant any Title of Nobility.
My understanding is that treaties between the United States and an Indian Tribe are the responsibility of the Commissioner of the Bureau of Indian Affairs in the U.S. Department of Interior (who reports to the Secretary of Interior who reports to the U.S. President).
Typically, the Commissioner of the Bureau of Indian Affairs would also be involved in the negotiations of interstate compacts in connection with the administration's recommendation to Congress regarding whether they would be approved, with a focus on not abridging any treaties between the tribe and the United States government and not violating the U.S. Constitution.
Different U.S. states allocate authority to different people. Usually, the Governor of the state, or a subordinate of the Governor in his direct line of authority would have the responsibility for negotiating the compact on behalf of the U.S. State. Any tribal compact with a U.S. state that is negotiated with an Indian tribe by the executive branch official in the state who is responsible, is subject to approval by the state legislature and Congress and the tribe.
Indian tribes also have different ways of allocating responsibility, but normally, negotiation would be vested in the hands of a tribal chief, subject to ratification by a tribal council.
The process for adopting tribal compacts with U.S. states is closely analogous to the process for adopting interstate compacts in the United States.