i am going to state the obvious but you have to start with a basic business license (about CNY3000 if you do it yourself, CNY5000 through an agent), then depending on whether you are looking to hire local staff only or local and foreigners, you might need a license to hire foreigners. there are different types of foreign employment contracts in china, in your case it would be educational and it is one of the most expensive and hardest to get.
not all the requirements are actually "written" in the law, but here are some of the things we were told by an officer at bao'an immigration office: at least two years of activity (thats a tough one for a new business), 400sqm of commercial space, one staff with 4 years experience at managerial level in a similar organisation, two qualified (i am not sure what the chinese qualification is called) teachers -cn-, and (this one is unconfirmed) between CNY300k and CNY500k in the bank.

there are "alternatives" -albeit nothing legal- and some people manage to go on successfully without the educational license but there is always a risk. we were fined CNY30K once for having an american teacher on our books. to us it was equivalent to eight months profit, so that did hurt. if you are in good terms with someone at the immigration office, you might get overlooked altogether when they decide to inspect organisation in the educational field.