It would help to know what your party looks like and the sort of resources (especially divination) they have available. These sorts of adventures can look drastically different with a mid-level wizard or cleric handy.
People being attacked through dreams provides some really interesting options to get around divination, though. Sure, you can speak with dead, but they'll just tell you about the freaky dream they had. Even more advanced scrying may not find the dream creature normally (depending on your cosmology, it's probably on another plane).
So, let's say your second stage is at a particular location. There's obviously going to be some connection between them, so that's one clue, let the remaining targets know they spent some time together there. Have the setting of the dreams where they die, if the players can talk to the dead, be another clue. And some hint at the murder scenes (wounds of a certain type, bodies turn up covered in water, witnesses mention a specific scent, etc.).
That's the sort of multiple routes thing you want. Put in three clues at each stage leading to the next stage and you should be golden.
Of course, even once they figure out what the victims did to attract the creature's attention, they still need to catch it somehow. I'm a big fan of making them attract its attention themselves, then fight it out in their dreams. But there might be other options, depending on its exact nature.
Cheers!
Kinak