Dennis Soemers' answer is correct: you should use a HashSet or a similar structure to keep track of visited states in BFS Graph Search.
However, it doesn't quite answer your question. You're right, that in the worst case, BFS will then require you to store 16! nodes. Even though the insertion and check times in the set will be O(1), you'll still need an absurd amount of memory.
To fix this, don't use BFS. It's intractable for all but the simplest of problems.
A much more memory-efficient algorithm is iterative deepening. It has all the desirable properties of BFS, but uses only O(n) memory, where n is the number of moves in the game.
Better still, develop a domain specific heuristic, and use A* search. This should require you to examine only a very small number of nodes.