Best data structure for queries about subsets?
There is a popular algorithm in bioinformatics for solving this exact problem. I believe it is known as the multi-set membership testing problem (MSMT).

BigSI

The idea in BigSI is that you represent each of the $N$ inserted sets as a bloom filter of length $m$ with $k$ hashes. Let $Q$ be our $m\times N$ table, where the columns represent each of the $N$ bloom filters for each of our $N$ sets $\{X_1, ... , X_N\}$. 

Now we wish to query $Q$ for an input set $S$. Let $A=\{h_i(s) \;\;\forall i\in[k],s\in S\}$ be all of the hash values for the input set. We have the following condition
$$S\subseteq X_i \iff Q[r][i] = 1 \;\;\forall r\in A$$ It remains to find columns such that the right hand side holds true. To do this, we create a subset of the rows  $Q'=\{row_i(Q) \; | i \in A\}$ . Now our condition is that 
$$S\subseteq X_i \iff Q'[r][i] = 1 \;\;\forall r\in [|A|]$$
i.e. any columns with all $1$s in $Q'$ is a superset of $S$. We can find such columns $C$ by performing 
$$ R = \bigwedge_{r\in[|A|]}Q'[r]$$
$$ C = \{i \;\;| \;\; R[i] = 1\}$$
If $C\neq \emptyset$, then $S$ must have been a subset of one of the original $N$ sets. Of course this algorithm is also able to tell you which of the original sets $S$ is a subset of. Since your question doesn't need that information, there may be some minor optimizations.

Here is a figure from the BigSI publication, where the input sets are FASTQ files which are broken down into $k$-mers. Part (a) represents the 5 input sets, each of cardinality 2. Figure (b) shows the resulting $Q$ table and the $\texttt{AND}$ operation used to find the superset inputs. Figure (c) is a naive alternative, where each row represents a possible element from one of the input sets, however this table would have to grow vertically as well as horizontally for each input set, as we may see new elements.