While it's not immediately clear on a first viewing, the pre-credits scene occurs chronologically after the majority of the scenes in the movie; Joel and Clem have already had their breakup, and have both erased each other from their own (conscious) memories. Note that Clementine's hairstyle is the same in the pre-credits scene as it is at the end of the movie: a blue color that's grown out substantially.
So the simplest answer is that their first meeting, when Joel's friends invite him to a beach party and Clementine is there, is in Montauk. If you accept this as true, then it makes sense that this location would have a special subconscious significance for both of them, and that they would be drawn to the same beach even after having erased their memories. However, one does have to accept Joel's memory as accurate for this to work; we only ever see their "first" meeting as part of Joel's memory, rather than in "real life".
However, there's another possible interpretation (which is why I put "first" in quotes above.) The final shot of the movie is a repeated shot of Joel and Clem playing in the snow at Montauk. Some people have interpreted this scene to mean that Joel and Clem have actually met multiple times before, and have erased each other from their memories more than just the one time we see in the movie. Viewed from this perspective, the ending is quite fatalistic: it seems to imply that people are trapped in destructive patterns in their lives, and that there's not a way to escape them. (To be fair, Joel says he's "OK" with that in the last spoken line of the movie.) If you buy this interpretation, then they have met in Montauk multiple times before the events of the movie, and so their subconscious draws them there even if they don't know why.
