It's a great journey that you want to undertake!
All the information about the Russian visa is available on http://waytorussia.net/Travel/VisaSupport.html
Generally, you can do the trip on a 30-day tourist visa, but you can also get a business visa, which is basically the same thing but extended (you can get it for 3 months and double-entry also). Both business and tourist visa take about 2 weeks to get once at the consulate but the business visa may be slightly more expensive. Also, the invitation for a tourist visa is issued in only 1 day while the invitation for a business visa might take about 2 weeks. I'd go with the business visa if I were you as it's more flexible, although a bit more expensive and longer to wait for. You don't need to book any hotels for any of those visas, the visa support themselves is like a preliminary booking, but you don't need to stay at the hotels listed there.
And yes, you can apply from Australia, especially if it's a business visa that you try to get.
Finally, regarding the stopover in Mongolia, definitely go for it! You might be able to get a cheaper train from Ulan-Bataar to Irkutsk or Ulan-Ude (a nice city to stop by in as well!) and if not you can always take a bus!