Better a late answer than none, ahem.
Qubodup already made a youtube video featuring walking sounds some time ago and I like to add some comments/reply and close this properly for now.
Of course I've had a look at that blog post for inspiration - otherwise it may be a bit over the top.
I used a stomp sound by qubodup, which I thought could be fitting, in the end I edited it to oblivion using audacity, adding more and more distortions and transformations - forming the shape of the wave to become a low tremor.
Within the simulation that sound is continously repeated - even when you stand still - the trick was to modulate the volume and pitch relative to the walking speed and the degree of ground contact. I think the results are quite reasonable - but it may become annoying over time - maybe it needs to be a bit more subtle.
As a comment to the video stated: Seeing the video and sound makes it obvious that the walking animation was kind of "slow motion" - so I've adjusted the animation speed to fit the audio.
I agree that it adds a lot to immersion and since then I've wondered why/that a number of open source games lack walking sounds.
They really do add value - you feel more connected than when just moving - floating - silently - and it really adds to the impression of a complete game.
The simple receipe is: Play steps in a loop and change volume (but this may be an issue for non-OpenAL-audio-libs) - or stop and start loop to be cheap.
Any half decent rpg and adventure game needs this
Gets me to another related topic: I'm still waiting for SDL 2.0 with force feedback version becoming the current release/stable version.
http://www.libsdl.org/hg.php tells it's under construction like may it be 2+ years since google sponsored force feedback development?
Would it be packaged and available I'd probably try it at least anyway.