www.stellarium.org/
See link above, critical resource. You download the program for free and then punch in your coords (Melbourne's is fine) and and then it will show you 360 degree views of the night sky in real time (i.e. what is directly above your head at night at that given time at that time of year).
I found a heap of stuff backyard observing using this program, Tuc 47, M45, M42, M31, Eta carinae, Jewel Box, Omega centauri, clusters around Scorpius, nebs around Sagittarius, it's a great program. Make sure you click on the nebula tabs and the constellation tabs at the bottom and it will show you where all (most?) of the DSOs are and it will also name them as you zoom in. Have a good look at the program and then go out and find them! Let me know how you go.
