I think you may have already seen my ideas on this subject, but for completeness, I think it's good to record them here.
I think the best results will come from using all sensors available. However, I got reasonable results from just using accelerometer data, see my answer here. What I did was to get a lot of friends to walk for me, and I counted how many steps they took. As they were walking, my Android device was logging all sensor output. I then developed a program in C# (because that's my favourite language) that analysed all the log files, and hence optimised a methodology for counting steps that I then ported to Android java.
Whatever sensors you end up using, logging a whole load of data and then analyzing to work out how best to count the steps is what I would recommend.