How do I legally set up an exchange? 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.