We provide a definition of Tanaka-Thomass Vafa-Witten invariants for etale gerbes over smooth projective surfaces using the moduli spaces of $mu_r$-gerbe twisted sheaves and Higgs sheaves. Twisted sheaves and their moduli are naturally used to study the period-index theorem for the corresponding $mu_r$-gerbe in the Brauer group of the surfaces. Deformation and obstruction theory of the twisted sheaves and Higgs sheaves behave like general sheaves and Higgs sheaves. We define virtual fundamental classes on the moduli spaces and define the twisted Vafa-Witten invariants using virtual localization and the Behrend function on the moduli spaces. As applications for the Langlands dual group $SU(r)/zz_r$ of $SU(r)$, we define the $SU(r)/zz_r$-Vafa-Witten invariants using the twisted invariants for etale gerbes, and prove the S-duality conjecture of Vafa-Witten for the projective plane in rank two and for K3 surfaces in prime ranks. We also conjecture for other surfaces.