Hello Rez,
I've found some reasonable dark places SE Melbourne. The
Melbourne Astronomical Society (whom I use to be a member of) use to have a dark sky site down at the Bass racecourse. To get there you simply follow Bass Highway towards Phillip Island. I'm not sure if they still use this site (usually Friday nights), but the skies down there are magnificent. Well away from much of the light polution. It takes approx 1.5 hr to get there.
I've been west to the outskirts of Kyneton a few times, but found they weren't very dark.
The hardest part of going to a dark sky site is the set up and tear down of equipment. If you are doing astrophotography, you find the accessories you need to carry with you dramatically increase. Perhaps I'm lazy, but this frustrated me to no end. I cracked and bought a farm South Gippsland, about 30 minutes out of Leongatha. I originally wanted a ten acre hobby farm for the dark skies, but the land I bought was too good to refuse, so ended up with 250 acres (a little extreme). This allowed me to set up a "base" where I could observe and image to my hearts content. The closest street light is about six kilometers away. No noticable light polution detected from the towns Leongatha or Mirboo North. Some day, I'll send out an invitation to all IIS members in Melbourne to establish a few star parties, astrophotography sessions or "Goto/computerise only" festivals down there. Bedding is limited in the homestead, but there is plenty of space to set up camp (250 acres worth!).
If you're not visually searching for faint fuzzies, there are quite a few places around Melbourne - Jells Park isn't bad.