As long as your app is working properly, you simply need to walk with the app open. It's more likely to work if you walk outside in a straight line (vs. inside in circles) since it is likely sampling your GPS location every N seconds to determine distance.
Your experience could be caused by the app getting into a semi-frozen state where you can still perform most interactions with the app, but some aspects are broken. Some indications of this I've seen include the animation in the upper-left corner going continuously and images not loading for pokestops.
I'm able to fix by killing the app and restarting. To kill the app in Android, open Settings, select the "Apps" menu, scroll down & select Pokemon Go, then touch "Force Stop". It will warn you that the app may misbehave. Say "Ok", then open the app normally---you should see the Niantic logo initially.