An excellent resource from the State Library of Victoria!
While this is an excellent site, I have found that using the search box provided on the site does not retrieve all the relevant results (at least at this stage).
For example, when I search for the surname Fullerton I receive 46 results.
However, there is another way to search this site which retrieves more results!
Go to Google www.google.com.au
and search for the surname you are looking for followed by 'site:gazette.slv.vic.gov.au'
For example, I typed 'fullerton site:gazette.slv.vic.gov.au' into the Google search box and Google found 554 results.