Well, they will be run as joint ventures between the national railways involved (and the train may go further afield still!) - so OEBB (Austrian), CD (Czech) and MAV (Hungarian).
From Prague to Vienna, you need to buy your ticket from CD, as OEBB will only sell tickets originating in Austria - see
here and select 'Praha' to 'Wien'. Note that only second class is available for advance online purchase here, but there's a huge price advantage in doing so: only US$28 for the journey.
From Vienna to Budapest, you can buy online from OEBB
here (there is an English option). Again, if you do a pre-purchase ticket, it's at a huge price advantage: US$26 for the journey vs US$74 for a walk-up first class ticket, but, unlike CD, OEBB will sell you a flexible first class ticket online. However, if you select a Railjet service (the premium trains from Austria to non-Highspeed destinations), then the premium classes are well worth it.
As concerns luggage, unless you have a ridiculous amount then, as with most trains in Europe, you just carry it on board with you. In an open carriage, there will be luggage storage at the carriage ends, as well as between back-to-back seats. In compartments, the overhead storage is more generous. Theft is rarely a problem, but if you're concerned, then take a wire lock to discourage opportunists - just lock it considerately for people joining the train later!
As for whether to pre-book, well... You'll save money, save time at the station and guarantee yourself a seat. You won't be able to get 1st class pre-booking on the Prague to Vienna leg, but I'm sure a concierge at any decent hotel could get the ticket for you, if that's what you prefer.
To get an idea of 1st vs 2nd class on the EuroCity trains doing Prague to Vienna:
Open 2nd:
http://www.railfaneurope.net/pix/hu/...Bpmz_belso.jpg
Compartment 2nd:
http://www.railfaneurope.net/pix/cz/.../CD_Bmz_in.jpg
1st:
http://www.railfaneurope.net/pix/cz/...051211_011.jpg
To get an idea of 1st vs 2nd class on the Railjet trains:
http://www.oebb.at/pv/en/All_about_T...ljet/index.jsp