Copied & pasted from my last gym headphone thread: iGrado's are the best solution i've found for using at the gym so far. I originally bought them for general listening, but they didn't get much use as they become quite uncomfortable after about an hour (as they clamp quite tightly to your head). I couldn't use them for commuting either, as they do leak sound - and although not a huge amount, it would be enough to annoy people around me. I then discovered they were almost the perfect headphones for gym use: rarely would a gym session last much over an hour, and they stick to your head throughout the most rigourous excercise. They also produce a good clean sound for the asking price, and the sound leakage is totally irrelevant in a noisey gym environment (you'd have to have them very loud before others would hear them). Also, if you like to train outdoors, their open design will probably save you getting run over.
If you've got a little more to spend, i'd go for the Audio Technica ATH-ES7. Although I haven't personally used them for gym work, they do apparently clamp quite tightly, offer good sound, reasonable isolation - and if you care - look very stylish.