Basically:
1. Register your connection through the WiFi settings on the beginning screen.
2. Have the Pal Pad and register your friend's Friend Code, and make sure they've registered your Friend Code.
3. Go to the receptionist in the basement of a Pokemon Center.
4. Battle or Trade with your friend. ^_^
Detailed-ish:
Nintendo Wi-Fi uses your wireless router(or the Nintendo adapter thing). You'll need the Pal Pad which shows up pretty early in the game. But first, on the beginning screen where it asks if you want to Continue/New Game/Mystery Gift/Import/etc there is a WiFi settings option. You can go in there to have your DS detect your wireless connection.
Now I'm not sure if you need the Pal Pad to access the WiFi settings, but that was the order I did it in.
Once you've set a default connection, open the Pal Pad in the Key Items pocket. It will have a choice to display your Friend Code. This will be the code needed for your friend, and you can give it to your friend to register you. To add your friend, click the Register Friend Code option and enter a name for your friend and then their Friend Code. Once you've done this you will be able to see each other when you go to the communications area in the basement of Pokemon Centers.
EDIT: Also, I updated the trading list on the previous page. The starters all have some nifty moves now. ^_^