You don't need special shoes. You can get the sensor from Nike stores directly or from lots of fitness stores (or just from Amazon) for $30. If you don't have an armband to hold your Nano + the sensor, I'd strongly recommend the
Marware Sportsuit Relay , which comes with a "shoe wallet" to easily attach the sensor to any pair of shoes. The Nano is shaped differently because of the receiver that is attached to it, so I'm not sure how well current Nano armbands/holsters will work.
Rob