Que est ici un équivalent soutenu de quoi qui n’est possible que parce que pas est omis. Une version plus courante est :

Je ne sais pas quoi vous dire, Mademoiselle !

Il s’agit ici d’une construction avec semi-auxiliaire [Grevisse, Bon Usage 14e ed. §§819-821, savoir est traité à §821 i)]. Autrement dit, le principe de base est le même que si la phrase avait été il sait parler français.
Ce qui complique la chose ici, c’est l’alternance possible entre quoi et que devant une interrogation indirecte dont le verbe est à l’infinitif (Grevisse, §732 b) 2°).

Par ailleurs, il tend à y avoir une nuance de sens qui fait que je ne sais que faire et je ne sais pas quoi faire ne s’emploient pas nécessairement dans les mêmes circonstances, mais il s’agit là d’une évolution encore en cours, et ici cette distinction est neutralisée.