This is a reasonable question, as the details in the paper are somewhat terse. My understanding is as follows.
In the bit-flipping problem, for a bit sequence of length $n$, the algorithm has up to $n$ states (tries/steps) to achieve the target state. Since the number of possible states is $2^n$, this becomes ridiculously large for growing $n$. Already at $n=30$ there are a billion possible configurations to choose from. This issue of large state space is compounded by the problem that the reward is always -1, even if the current state differs from the target state by a single bit, i.e. there's no relative measure of closeness (i.e. a shaped reward function, such as the difference in bits between current and target state). So, despite learning transitions (i.e. how to get from one state to the next), there's essentially zero learning achieved unless the algorithm gets lucky and hits the target state, which happens with exceedingly rare probability as $n$ gets large. Moreover, even for small $n$, it still needs to wait sufficiently long enough to hit the target state.
The purported solution is as follows. Define secondary goals $g_i$ to be reaching previously visited states. So in the above example, you run the algorithm and get a sequence $(s_1,\cdots,s_T)$ along with the actions you took, which did not achieve your goal of $g$. You instead define a new goal $g_1=s_T$, and then sample from a set of goals $(g,g_1)$ via plugging these goals along with the last observed actions into the RL network. Since your sequence did achieve $g_1$, there is something learned here, in particular about the transitions $(s_1,\cdots,s_T)$.
This toy example is a little frustrating because in this case, you're very conveniently replacing the desired goal by a morally equivalent goal of getting to a different state (i.e. by "resampling" your training data). Whereas the goal of the paper is to apply this technique to problems where the auxiliary goals are less clear. Thats why I think the overall message here is how to quickly learn the possible action state space transitions, so that you can more intelligently explore your state space, as opposed to just randomly trying things in the beginning as you never actually observe the reward.
The paper gives a good example of robotic arm training, where a shaped reward function might be detrimental to the algorithm: penalizing moving away from a cube might be bad in situations where the arm needs (would benefit) to make a maneuver that temporarily increases the distance from the cube. In the example of picking up a cube, since everything is done in simulation, you can check if the algorithm could have picked up a cube at state $s_T$ (and I think also $s_1,\cdots,S_{T-1})$.
