Root Beer (& Creme Soda) seems to be an art form much like ales, lagers and such. You'll see some breweries that will also venture into root beer. Most of the time they have many more ingredients in them than a more complex stout. There are kits to be had that make it simpler (syrup & carbonate) but as mentioned being in Australia you may have a more difficult find. I'd do some google searches (homebrew Root Beer) and start there. I was intrigued once as well on Root Beer as I like it as well but it started looking like so much work and no buzz I opted out
Check this recipe I saw on BYO.COM (Alc and non-Alc).
5 gallons, partial mash
2 lbs. crushed mild ale malt
1 lb. dark crystal malt, 120° Lovibond
0.25 lb. black malt
0.25 lb. chocolate malt
3 lbs. unhopped dark dry malt extract
0.5 lb. dark unsulphured molasses
4 oz. maltodextrin powder
1 oz. Cluster hop pellets (7% alpha acid), for 60 min.
0.5 oz. sassafras bark
0.5 oz. sarsaparilla bark
1 oz. dried wintergreen leaves
0.5 oz. shredded licorice root
pinch sweet gale (optional)
pinch star anise (optional)
pinch mace (optional)
pinch coriander (optional)
dash black cherry juice (optional)
10 to 14 g. dry ale yeast
2 oz. lactose powder
7/8 cup corn sugar
0.5 cup spice tea (pinch wintergreen, sarsaparilla, licorice root)
corn sugar for priming
Step by Step:
In 1 gal. water mash crystal, black, chocolate, and mild ale malts at 155° F for 60 minutes. Sparge with 1.5 gals. at 170° F. Add 1 gal. water to kettle and bring to a boil. Add dark dry malt, maltodextrin, and molasses. Stir well to avoid scorching. Add Cluster hops and boil 60 minutes. At kettle knockout steep your spice combination (in a mesh bag) as wort cools. Pour into fermenter and top up to 5.25 gals. Cool to 75° F and pitch ale yeast. Ferment seven to 10 days at about 70° F, rack to secondary, and condition at 60° F for two weeks. Prime with corn sugar, add strained spice tea (1/2 cup boiling water over spices for at least a half hour), and bottle. Age two to three weeks cool (55° F).
Alternatives and Options:
Non-alcoholic creamy version: Instead of fermenting the wort, cool to 75° F, substitute 5 to 7 g. dry champagne yeast for the ale yeast, and bottle immediately. Store at 70° F for two or three days, then refrigerate. Follow these instructions exactly, otherwise you risk exploding bottles. You may also use ale yeast, which is somewhat safer because it will not continue to ferment in cold temperatures. However, the bubbles will not have that fine champagne quality. A safer way to carbonate: Get a CO2 system and either put your root beer in 5-gal. soda kegs (force carbonated) or get Carbonater-brand couplings and bottle in 2-liter PET bottles (force carbonated at 25 to 28 psi, chilled and shaken well).