Finding an apartment on its own doesn't justify this being an expat question, but since I've done this myself AND know there are some expat issues with doing so, I'll address those.
It takes time. Many agents will just add you to their email lists for listings. There might be some who will take you around, but most just run open homes and deal with the paperwork (in my experience). In Australia, open homes are often on a Saturday morning, and the agents just won't let you see it another time. So now you have 5 you want to see between 10am and 12pm, which isn't possible as they're all over the city, so you pick and choose say two. Then you get there and find one is under offer, and basically the whole process is painful.
However, this applies to locals too. What differs for expats is the application forms. You're expected to provide recent addresses, sometimes references, and history of your former tenancies. This gets tricky as you have no local history for them to verify with, and many are reluctant to call overseas to check references. However, respectable agencies should do this, it's just a concern with say, independent owners.
You also are expected to provide what is referred to as 100 points of ID. Usually a passport and Aussie driver's license gets you pretty far, but other aspects of this include bank statements, previous utility bills in Australia, and so on. A letter from your company proving your employment, as well as your salary (contract will suffice) is invaluable in meeting these requirements, as is getting a bank account ASAP (you can walk into CBA and walk out an hour later with a bank account).
When I moved to Melbourne from Vancouver, it took me 2-3 weeks to find a shared place that I wanted, and even then, it wasn't available for a couple of weeks. So even if you find the place you want, it might not be ready for you immediately.