You need to decide first what type of headphones you would like: In-ear types, buds, or std headphone cans (either open or closed).
I personally replaced my iPod buds with a pair of Shure E2C's, which fit directly into your ear canal, sealing off the outside world with foam (my choice) or soft plastic covers. Fitting them takes a little practice, but after about a week I got the hang of it and no longer need to stand in front of a mirror to install them. The sound is superb, bass response exquisite, you are not distracted by outside noise and neither do you irritate fellow commuters as sound leakage is minimal.
Well thats my suggestion but as I say, knowing what kind of headphones you would be comfortable with would be a good first step to narrow down your search.
Vanilla