They do, because all the states existed (as colonies) before the country of Australia and the federal parliament were created. When the states joined together and created a country and a national parliament they each gave up a little bit of their power to give the national parliament something to do (eg currency, immigration, etc - these are the specific powers listed in the Commonwealth national constitution). Everything they didn't give to the federal parliament they just kept.
If you read ss106-108 of the Commonwealth Constitution it recognises that the states had constitutions, laws and powers of their own prior to federation, and acknowledges that the states keep all of this after federation (except for the few powers they gave up).
The states need to have their own constitutions, though, because they each need a document to set up their parliament, government, governor and courts - the federal constitution doesn't do any of this for the states (because it didn't exist when they were created!).