Under Taxes -> Zone definitions
I have 1 tax zone definition set up (Australia)

Within that "Australia" zone that I have created I have 1 sub zone
-> Country = Australia, Zone = All Zones.
(I've also tried listing every state of australia individually as a sub zone of Australia so my Australia zone had 8 (state/territories) sub-zones.

Under Taxes -> Tax Classes
I have one tax class called "GST"

Under Taxes -> Tax Rates
There is 1 tax rate.
Tax Class Title=GST
Zone=Australia
Tax rate=10%
Description=GST
Priority=1
(It was originally Priority=0 - neither seems to change the result).

All my items in my shop have my tax (GST) applied to them.

When a customer signs up to my shop, if they are in the same country state (New South Wales) as my shop, everything works correctly.
However, if the customer's address is in a state/territory of Australia that is not New South Wales, prices in the shop show up without the 10% GST supplied. Also, when they go to checkout, the tax=0.00%, price(inc) and price(ex) are identical (ie. the non-tax price which is 10% lower).

I can reproduce the problem by creating a new account for my store where the state of the country is not New South Wales, then viewing any item - they show without the tax, so it's not something that only applies to the checkout.