According to the document detailing the plan put out by the Austrian ministry for Social Affairs, Health, Care, Consumer protection, it will be enough to have received the first injection, if that happened at least 22 days earlier:
Sobald die entsprechende Rechtsgrundlage geschaffen ist, werden auch geimpfte Menschen von der Testpflicht ausgenommen sein. Dies gilt ein Jahr lang ab Tag 22 nach der Erstimpfung.
By contrast, in many countries (and, possibly, to return to Germany more easily), “vaccinated” means having received all a full vaccination course (i.e. two doses for most vaccines).
The rules for entry after May 19 have yet to be finalised but the border with Germany already opened a little bit on May 13. For people who have not been outside of Germany and Austria in the last 10 days, it's possible to enter without test or quarantine if you can show you have received at least one vaccine injection.
Anerkannt sind alle von der EMA zugelassen Impfstoffe. Eine Impfung gilt ab dem 22. Tag nach der Erstimpfung für maximal 3 Monate. Nach der zweiten Teilimpfung verlängert sich die Gültigkeit um weitere 6 Monate. Bei Impfstoffen, die nur eine Impfung erfordern, gilt diese ab dem 22. Tag.
Unlike what was suggested in the earlier plan, this exemption is only valid for 6 months after the injection (vs. one year). The Austrian government now calls this the 3-G-Regel for Getestet, Geimpft, Genesen (or, in English, “tested, vaccinated, recovered”). For now, you also need to register electronically before crossing the border and the ongoing lock-down still makes tourism difficult.