Over 3G you have to play online. It's easy to find each other (rooms are named) but up to 4 peole can join, so if it's you and your friend you're liable to have 2 strangers joining you.
It's also possible to set up a local wi-fi game, though. In that case the game is limited to people on your personal network.
Touch4: FS5 is another app that runs over Edge and 3G. If your curious, it's a connect 4 clone and is good fun. I do believe it's free now. It was $5 a couple of months ago when I bought it.