This page is outdated. Since the new "Hauptbahnhof" has opened, it is now usually fastest to take the train (at the airport train station marked OeBB) to Wien Hauptbahnhof and change to a train for Graz there.
Direct trains from Vienna to Graz leave "Wien Meidling" train station every hour, departing 3 minutes after the full hour (first 6:03am, last 9:03pm). The trip takes 2h30min. Look up train schedules on the OeBB website. Note that Vienna is called "Wien".
You can look up the entire connection from Vienna airport to Graz, including public transportation between the airport and Wien Meidling train station, on the OeBB website mentioned above. Enter "Flughafen Wien" to "Graz". If the software says something annoying, like, your entry is ambiguous, just persevere and say "enter" one more time. Once you have found connections, click on the red arrow on the left to see details about changing subways.
You can buy train tickets Vienna-Graz from a red OeBB ticket machine (not the green ones of Vienna's public transportation system) in any train station in Austria, in particular at Wien Meidling station and at the "light rail" (Schnellbahn) station (not the CAT stop) at the airport. You can also buy an eticket on OeBB website. Regular price Wien Meidling to Graz is Euro 37 one way. The return ticket is no cheaper than two one-way tickets. If you buy an eticket a long time in advance on the OeBB website, you can sometimes get "Sparschiene" tickets for as little as Euro 9 one way. Tickets do not include a seat reservation. If you are morbidly afraid of not finding a place to sit, you can buy a reservation separately.
Note that Wien Meidling train station goes by many different names in the public transportation system: the airport bus's stop at this train station is called Dörfelstrasse; the subway (U6) stop is in the process of being renamed from Philadelphiabrücke to Bahnhof Meidling and the light rail (Schnellbahn) stop is called Wien Meidling.
To get from Vienna airport to Wien Meidling train station, you have several options.
The simplest is to take the airport bus to "Dörfelstraße". The busses depart from the airport at the full and half hours xx:05 and xx:35, between 6:05 and 23:35, see airport bus schedule. Duration of trip from the airport to Wien Meidling 30min, cost Euro 8. (The bus goes on to Westbahnhof after stopping at Dörfelstraße/Meidling. The 45min mentioned on the postbus webpage refers to the whole trip from the airport to Westbahnhof.)
The cheapest option:
You can take the light rail Schnellbahn.
Take S7 from the airport in the direction "Wien Floridsdorf";
change at "Rennweg" to S2 in the direction "Wien Meidling".
Duration of trip: between 39 and 44 min. Departure at xx:17 and xx:42.
As Schnellbahn is part of Austrian railways OeBB, you can
and should buy a through ticket to your destination,
"Flughafen Wien to Graz Hbf":
It costs only Euro 1.80 more than the
ticket from Wien Meidling to Graz.
Map of subway and light-rail network in Vienna
If you use light rail S7 from the airport to Vienna (not connecting to
an OeBB train, but going on to some place in Vienna by public
transportation), you have to pay for 2 "zones", or punch 2 zones
on a 10-zone ticket.
The most expensive option: Take the "CAT" airport train to "Wien-Mitte Landstrasse". There, change to light rail S3 or S9 to Wien Meidling. Or change to subway U4 (direction to Hütteldorf), change again at Längenfeldgasse to U6 (direction Siebenhirten or Alterlaa), which goes to Wien Meidling. Departure of CAT from the airport is xx:05 and xx:35. Cost of CAT is Euro 11, plus you need a ticket for the subway or light rail. You can buy a combination ticket CAT plus public transportation in Vienna at the ticket machine. The CAT airport train is advertised in the baggage claim area of Vienna airport as if it were the only mode of transportation to Vienna, but the airport bus or light rail are almost always the faster connection to Wien Meidling train station.
You can search for connections from Vienna airport to Wien Meidling train station on the website of public transportation in and around Vienna by typing "Flughafen Wien" to "Bahnhof Meidling". Searching on the OeBB website for "Flughafen Wien" to "Graz", however, finds most of these connections, too, and selects the best one for catching the next train to Graz. More details on public transportation strictly inside Vienna here. Maps of the Viennese public transportation system under "Netzpläne" in the pull-down menu "Fahrplanauskunft".
Once Vienna's Südbahnhof (south train station), currently under reconstruction, will reopen under its new name Hauptbahnhof (main train station), it is to be hoped that there will be direct trains from Vienna airport to Graz.