That's one of the things that got me into Geology...fossils. Being a geo' I keep my eye out for any interesting places when I go bush. I've collected quite a few fossils in my time...corals, bits of lycopods Glossopteris and tree ferns, nautiloids, brachiopods, crabs and prawns, fish etc. I can take you to some out of the way places not many people know about
If you like the big stuff, not more than 100 miles from home there are Diprotodon, Procoptodon, Thylacoleo and other fossils...mostly Dip's, though, and about 250km NW there's Megalania and snake fossils.