>You got to have that person on your pal pad. Then you have to edit the privacy setting in Pokemon.com, enabling either Everyone or Friends Only to be able to see you.
You need to add them on your Pal Pad first. That's the only way. An email to Nintendo also states this:
>At this time, there is no available search function to find Game Pals in the Dream World. However, we know this is a popular request and we have reviewed and recorded each one to pass along! Keep in mind, though, multiple requests will not help expedite these requests, but your enthusiasm is appreciated.
Source
