The Long Distance Bus Station is at the northwest end of Jiefang Road near the intersection with Ahemaitijiang Road.
Almaty, Kazakhstan - takes about 12-15 hours, but apparantly no direct buses
Altai City via Burqin - takes about 48 hours
Chorgas - Small bus ¥25, Large bus ¥?. Use this to cross the border to Kazakhstan by foot. Takes about one hour after which you can walk to the border by foot in ten minutes. Once through the Chinese passport control and customs you must use a bus to travel over the border for ¥20. Bribes appear to have been formalised so that you need to pay a further ¥20 after the bus departs. On the Kazakh side there is another little bus that apparently costs 500 Tenge to take you to the taxi-stand. Do not forget to ask for your (apparently) free registration at the Kazakh border, you need two stamps on your immigration card for this. Otherwise it costs 767 Tenge, atleast in Almaty, to register. It is not really necessary but can save you a lot of hassle with corrupt officials.
The police and the military are pretty touchy in Yining. No taking photographs of mosques and obviously don't take pictures of the military. The hassle is mainly due to them being confused how to deal with foreigners - best option seems to be to ask them to take you to your hotel, who can clear things up in about a minute.