The simplest solution would be to have a time-window and a number of thresholds. The signal gets a form of a double wave, and you can split a step into several parts. You may need to have several windows and corresponding threshold values to recognise one step. But keep in mind that this signal will change if someone is walking upstairs/downstairs or running or just walking with different pace. You will get great variability if you actually going to try it with several participants.
Threshold values will differ greatly between devices. Frequency of measurements will also have an impact. Standard frequency that allows one to detect walking with normal pace is about 10Hz, some devices use 20Hz, if you go over this you will get lots of data and little information. Manufacturers do use different versions of accelerometers, so if your software works on one phone, there is no guarantee it will work on the other device even of the same model.
I would start from plotting your signal first. Also don't forget that the phone can be in different positions in a pocket (unless you fix it somehow) so the threshold values will float. All clinical pedometers are usually affixed to the leg in a certain position.
Consider using mono-axial accelerometry instead of 3-axial, the signal analysis gets much more easier to begin with. Also take a look at the Fourier transformations and wavelet analyses.
See the image below to get a basic idea of how walking looks with a 3-axial accelerometer. I made it when was doing similar task (walking is the noisy bit).

And this is how walking looks with a mono-axial accelerometer (again noisy bits)
