How does someone establish a stock exchange?

Is it like establishing a newspaper, or is it necessary to receive authorization from a government agency before operations begin? If prior authorization from a government agency is required, then perhaps stock exchanges aren't a good symbol for the free market.

The one that pays McDonalds millions to train people in their zero-training model?

The one that pays 50% of agricultural subsidies to corporations that drive small farmers and ranchers out of business?

Perhaps the one that loans trillions of dollars to hedge funds and insurance companies to pay their million dollar salaries and billion dollar returns when they bet that the government wouldn't let them fail, while leaving perhaps as many as 29 million Americans unemployed?

The "free" means that government and business are free to craft a life for most people who will live within a fantasy that they have as much opportunity as anyone else, while their labor is used to provide excessive wealth to other people.

....sorry, when I see the words "free market" it just makes me want to question the myth... ;)

But in answer to your question - for an exchange, you must abide by SEC rules as well as several other laws. You can "make a market" for "over the counter" stocks, (so-called penny stocks - that is companies that have so little capitalization they cannot be traded by the major exchanges, such as the small, local paint manufacturer) by insuring that there is a place where they can be bought and sold, but they are also subject to SEC rules, though there does seem to be less regulation.

then, you pay off the right government officials, and presto! your own exchange.

There is a lot of regulation of the stock market, and the exchanges would have to comply with all those regulations. Whether there's a separate authorization process might be a secondary issue.

If your definition of free market means no government regulation or involvement, a stock exchange is certainly not a good example. There are few businesses that are completely free of the government.