While grammarians have come up with quite an elaborate classification system for genitives, most of them come down to the same thing: when one noun is modified by another in Latin, the modifier takes the genitive case. Genitives of quality, price, partition, and so on are just special cases of this.
So what this really conveys is that "rebirth" is modifying "bath" in some way. The easiest way to capture this in English is to use "of": they need either "a bath of rebirth" (i.e. water baptism) or the desire for one.
Another way to convey this in English is to put the nouns next to each other with no preposition: "a rebirth bath". This doesn't sound as good to me in this context.