For each position in the game graph, Freecell Solver maintains a data structure which identifies it called fcs_state_t. This contains the cards in the stacks and the freecells, and the value of the foundations. The stacks and freecells are uniquely sorted to avoid states that are identical except for a different permutation of the stacks or the freecells.
fcs_state_extra_info_t contains a pointer to the fcs_state_t which it is associated with, and defines some other data. The real locations of the stacks and freecells are stored there for instance, as well as some graph information. See Canonisation and Normalisation in the terminology.