Let me give this question a try. I am not sure I do fully understand it so I was considering to post a comment but in the end, I preferred to try an explanation. Hope it helps!
Raphael already suggested a solution (so I voted up his comment) which works even if you only store states instead of nodes. To make it clear:
- states: those in the original problem. These are unique
- nodes: those enumerated by your search algorithm (bidirectional breadth-first search in your case). As stated in your book "two different nodes can contain the same world state, if that state is generated via two different search paths" so that it is very likely to have more nodes than states (since the former distinguish states by the different paths ---which can be exponentially large--- that lead to the same state).
Obviously, the path from the start state $s$ to the target $t$ is computed by concatenating the paths from $s$ to $n$ and from $n$ to $t$ where $n$ is the node that was found in the hash table of the opposite search.
Now, assuming you are using a consistent-heuristic function (a heuristic function $h (n)$ is said to be consistent if and only if it satisfies the triangular inequality $h(n) \leq c(n,m) + h(m)$ where $c(n,m)$ is the cost of the operator from node $n$ to one of its offsprings $m$) or no heuristic function at all (so that your BFS is a blind search) let me suggest the following procedure:
Let me assume wlg that $n$ was generated by the forward search (i.e., from the start state $s$) and that it was found in the hash table of the backward search (i.e., the one issued from the goal node). In this case it suffices to expand the node $n$ and to select any descendant that appears also in the hash table of the backward search. You can do this since you are storing all states (instead of nodes) in both hash tables. No matter of the difference between nodes and states, if you generated $n$ in the backward search (which results from the fact that it is stored in the hash table) it had to be done via one of its parents which can be recovered now as one of its descendants (assuming you are traversing undirected graphs, otherwise just apply the inverse operators to recover the parents). Acting like this you will eventually get to the target node.
The same mechanism applies to the forward search ---i.e., no need to store with each node its path to the start node, just use the closed list implemented as a hash table. Reverse the path obtained in the previous paragraph, concatenate them and there you are a solution path.
If you are not using a consistent heuristic function, then you should store along each node in the hash table its value $g(n)$ ---i.e., the cost of the path from its corresponding root node, either $s$ or $t$. Doing so, the previous procedure is just slightly modified by selecting the parent (now generated as a successor) whose $g$ value is $g(n)-1$. However, this is not even necessary in case you are seeking (as it seems) any path from $s$ to $t$.
Bidirectional search is one of the most intriguing "paradigms" in heuristic search. Noone has already found a simple way that makes it as efficient as in the case of blind search (where it is clearly a winner).
Hope this helps,
