One way of (somewhat) formalizing this is to say that you have a set containing infinitely many rooms, and another set containing infinitely many tenants. Intuitively, it does not seem unreasonable that you can give every room its own tenant. Once you do this, then the hotel is "full" in the sense it is impossible to find an empty room.
Of course, we can also think about giving each tenant her own room, which also seems possible. If we can do both of these things, we say that the set of rooms is the same size (or cardinality) as the set of tenants. It is worth noting, that not all infinite sets are the same size [0]. For the purpose of Hilbert's paradox, I believe it is far to assume that we are dealing with countably infinite sets [1]. The mathematical result in Hilbert's paradox is that if you add elements to a countably infinite set, the result is still countable infitite.
[0] https://en.wikipedia.org/wiki/Cantor%27s_diagonal_argument
[1] That is to say, sets which are as large as the set of natural numbers.
N1 = { 1, 2, 3, 4, 5,... }
can be set into a one-to-one relationship with the set
N2 = { 2, 3, 4, 5, 6,... }
by the function
f(n1:N1) -> N2 = { n1 + 1 }
(Using a notation I pulled out of my flying monkeys right at this moment.)
The first set, N1, is the state of the hotel with one guest in every room, i.e. { n | room n is occupied }. The second set is the state of the hotel after Mr. Hilbert's operation, with room 1 empty.
The meta-trick is that an infinite set can be put into a one-to-one relationship with some proper subsets of itself (that's one definition of "infinite", by the way).
Imagine: how could the proprietor even communicate with those infinite guests?