I'm asking about legal concerns, not technological ones. If I'm based in the USA, should the exchange be a US company? If not, where should it be based?
How is banking set up?
I don't think StackExchange is the best place to ask for legal advice.
Logically, one would set up a company, get a business bank account and start their operations. However, it is very advisable to consult a lawyer first, as there are some legal concerns one should keep in mind, like the money laundering regulations that one should adhere to.