Based on some of the websites I looked at for each country, it appears to early for me to book anything at the moment.
Yep, in regards to your itinerary it's more about 92-60 days (depending on connection) in advance ticket sale, so you won't be able to purchase tickets for May up till February-March. Though nothing to worry about here, it's a standard practice with almost all the railways companies in Europe
But I was wondering if I could get some help with estimated costs
Well, there is a relatively easy way to find out estimated costs - you simply look for dates around two month in advance from now (like mid January). Cheapest options are usually special discounted point-to-point tickets, which are sold in limited number per departure, it's a sort of promo fares (usually something like 19, 29, 39, 49 etc. euro). But let's look at each leg:
Amsterdam-Berlin: daytime direct InterCity trains (roughly 6 hours journey) start from 39 euro. And there is also a overnight CNL train which start from 43 euro (seats), 59 euro (couchette) and 104 euro (sleeper). You can see timetables and purchase tickets via official
German Railways (DB) website. If you can't/don't want to purchase your tickets in advance, then it's also possible to travel relatively cheap (comparing to full standard fare 110 euro) with tickets bought before departure, but it might involve some tricks and train changes
Berlin-Prague: again German Railways website is your helper here, but this time discounted tickets start from 29 euro (usually sold out later than cheap Amsterdam-Berlin ones)
Prague-Vienna: same idea - discounted promo fare tickets, but this time from
Czech Railways website eShop, start from only 19 euro per person. With Prague-Vienna journey you again can omit buying discounted tickets in advance, but again then you'll have to do some tricks in order not to pay full fare (60 euro)
Vienna-Budapest: and again discounted tickets is your choice #1, start from 19 euro and can be bought via Austrian Railways website. A guide on how to do it -
http://europetrainsguide.com/Advice/How-to-Buy-Train-Tickets/Austria-OeBB.htmlAs you can see, smartly and on time purchased tickets can actually allow you to spend only around 100 euro per person (app.130 AUD) for the whole itinerary (4 journeys), which is actually a good price for such type of travel plans. Also, if it's more convenient for you (like cheaper rates to fly out from), it's possible to switch a bit the plan and do Amsterdam-Berlin-Prague-Budapest-Vienna
So, as of now, we advise you to take a look at all the mentioned websites, check all the fares etc. and if you have any further questions, we will be glad to help
p.s. due to shorter distances in case of the last three legs (Berlin-Prague, Prague-Vienna and Vienna-Budapest) you can also rely on rather cheap buses, it can cut your travel expenses even more. With Amsterdam-Berlin you also can catch not very expensive bus, but it's less convenient since the distance (-->travel time) is already essential, so train is much more comfortable