Data-structure for dynamic disjoint-sets
For Magic the Gathering, the number of cards is so small that the simplest data structure is probably the best.  Just have a list of all cards (each card records its name, location, properties, etc.).  Then to answer a query, scan through all cards and see which ones match the query.  Since you'll probably have very few cards in the data structure at a time (like, at most a few hundred), all operations should be very fast.

There are more sophisticated schemes, but they probably aren't worth the implementation effort.  You could think of this as a table in a relational database (one row per card, one column per attribute), and build an index for each column.  In other words, you have an ordered list of cards.  You also have a hashmap that maps from location to a list of all cards in that location.  These lists are stored as balanced search trees, with links between them (i.e., given a card in one tree, you can follow pointers to find where that card is stored in each of the other trees). This will let you do queries quickly.  Also to update the data structure, you can remove a card by finding it, then removing it from all of the linked trees; and you can insert a card similarly.  But in your case it won't be worth the effort.