We don't know what they are. We know what we mean by the term Qualia, but we do not know what their nature is.a
That’s just an assertion, and there is no we that includes me as I do not know what their “nature” is.
As for how I know that everyone has them, I use induction : The only particular example that I know of (me) has qualia . I can use induction to establish that probably all humans have qualia.. Then say that if I meet another human, he probably (only probably) has qualia. Therefore, solipsism is probably false.
By analogy , when scientists find a fossil with a small skull, they say that probably this is average size of these species. Because the odds of it being a deformed skull are very tiny. It's more meet people with an average height, than exceptions. So, Probably what I see is the norm.
I can use the same induction to claim there are no qualia as the only particular example I know of (me) doesn’t seem to have this thing (a thing that apparently can’t even be defined in a non circular way).