Hello Peter,
If your ancestors Johann C Barthold aged 40, his wife Caroline aged 42 and their son Paul W aged 4 years, migrated from Schönberg in 1871 and arrived in Melbourne from a British port in February 1872 per the "Great Britian", they were possibly not assisted immigrants. In other words they most likely decided to emigrate to Australia because of the economic difficulties in Mecklenburg when Bismarck unified Germany in 1871.
Bismarck discouraged emigration 1871, his restrictive practises were enforced by 1874 effectively stemming the tide of legal emigration. Immigration Agents in Germany always competed to offer the best deals and conditions for the voyages to Australia. As your ancestor was aged 40, married with young son he would have been eligible to leave because of his age.
Once a passenger agreement was made agents usually arranged for the transport of large groups of travellers from certain cities, according to their destinations. They travelled by train and or river boats to a suitable port either in Germany or one of many other ports in France, Belguim or Holland.
This would have been an all inclusive cost, overnight accommodation may have been provided in often called immigrant barracks on route.
The shipping companies either owned or charted ships for the voyage to England from Europe and owned hundreds of ships that sailed to the various ports in southern hemisphere including Australia on a regular basis. Britain ruled the waves and were experts in transporting people to Australia since the convict era.
From the mid 1850s to the start of WW1 thousands of un assisted German immigrants including professionals, businessmen, engineers, clergy, farmers and labourer's etc. arrived in Australia from British ports. Government assisted immigrant schemes in Australia and New Zealand gradually become redundant during 1870s.
If as you said you have all their papers, permission to leave must have been granted, so you must have a departure date from Schönberg in 1871. Have you checked the Hamburg INDIRECT Departure List Index for 1871 ? LDS Film 1049011. Indirect passenger lists (with indexes) record passengers who stopped at other European or British ports before sailing on to their ultimate destination usually on another vessel. If your ancestors did leave from the port of Hamburg for England their names could be on the index.
However if they sailed from Bremen then there are no passenger lists for that period because the Bremen archives destroyed them in 1908 because of lack of space. Many other archives world wide did not place any historical importance on heaps of records created in the 19th century sadly, they are missed greatly by many researchers. You should be grateful that you do have a record of their arrival in Australia, many researchers are not so lucky.
The Church records are available from the LDS (Mormons) see details below.
You can check for further details by doing a place search on the LDS Library catalog
Kirchenbuch, 1799-1896
Evangelische Kirche Rossow (AG. Röbel) (Main Author)
Mikrofilme aufgenommen von Manuskripten in Goslar.
Parish register of baptisms, marriages, and deaths for Rossow (Dosse), Mecklenburg-Schwerin, Germany. Includes Netzeband and Schönberg.
Germany, Mecklenburg-Schwerin, Schönberg - Church records
Schönberg: Taufen, Heiraten, Tote 1799-1896 - FHL INTL Film [ 69522 ]
I hope this helps and you have some luck on the LDS films.
Elizabeth