How can I wirelessly connect the NXT and an iOS device? I've seen videos around YouTube (like this one for a car) that show an ability to control a Mindstorms set via iOS (either iPhone or iPod Touch).  I am just getting started with Mindstorms, but find this type of possibility very intriguing. How can I set this up? Should I use Bluetooth or something else?
As stated in the description of that video, the big issue is that the iPhone won't pair with uncertified devices:

The car is built with standard Lego Mindstorms NXT components. Since iPhone SDK does NOT allow using non certified devices (which are limited to other iPhones and some headsets etc.) I have used BTStack library.

I guess this is why there's an official app for Android, but not iPhone.
Note that the app itself is only available on Cydia, which I believe requires a JailBroken iPhone to run:

LegoDrive is available on Cydia. Just install using Cydia on your iPhone/iPod, enter your Lego NXT's device ID and you can use LegoDrive too!
LegoDrive (formerly presented as iCar) demonstrates how to control a Lego Mindstorms NXT robot using (rotating and tilting) iPhone over Bluetooth.


Edit to add (08-Jan-2013)
The recently announced Mindstorms EV3 includes the statement that:

LEGO MINDSTORMS EV3 will also include full iOS and Android compatibility out of the box.

While the new &quot;EV3 Intelligent Brick&quot; features:

New Linux-based firmware, a USB port and SD expansion slot [which] offer nearly unlimited programming and expansion capabilities