Good question!
All you need is the sensor, not the dock connector. I purchased mine at the Apple store for $19.00 when I bought my 3G S. If you look in Settings->Nike+iPod you can enable it on the iPhone. When you enable it, it adds the Nike+iPod app to your apps page.
One thing I have noticed is that when you get an incoming call, the workout stops. Has anyone else noticed this as well?
I bought a DLO packet that Velcros to the shoelaces and holds the sensor when needed. No need to buy special shoes for it.