If my company is in Australia, I sell into anywhere and the work is done anywhere who's taxes should apply?

Basically as the title suggests, the tax situation is getting grayer over time as new business models emerge.

We are considering one where the app is hosted "somewhere", the company is currently in Australia but doesn't have to be, the work is sourced from all around the globe and payments are coming in from any currency ...

Where should I setup the company for best effect?
Are there any restrictions on where it is setup?

You need to talk with an attorney who specializes in international taxation. It's an incredibly complicated and weird field that changes all the time, and I wouldn't take any other advice you get here with anything but a huge grain of salt.

For instance, we're currently having a huge political squabble here in the States about US-based multinationals having squirreled away about $1 trillion in profits in lower-tax countries, and wanting a special amnesty to repatriate that money to the US without having to pay the difference in taxes.

of course, off shoring is best. however your primary country of citizenship (Australia, i presume) may have objections to ownership of companies in 'off shore'. probably not, but do check.

other than that, i feel it is a huge hassle to off shore a company in early stages, and you are much better off starting a company in your primary country of citizenship. you can always move it later. the laws of the country of origin of COMPANY apply in all transactions with customers. in b2b laws which are agreed upon apply (but usually, also in the primary country of establishment of one of the companies OR the country where the work is being done if elsewhere).

What matters is where the company is formed. That will dictate the taxes that apply. Talk to an accountant in that state/province/territory. They're the only ones who can give you accurate information.