You start from noise or noisy sounds (e.g. inharmonic FM or AM) and then you further shape them by filtering. That's the basis. Wavetable or other forms of "synthesis" could do as well, but those aren't technically synthesis, because they work on prerecorded audio.
To make a complete footstep sound or multiple different footstep sounds is however too or unnecessarily complex to be attempted to be done inside most synths (it would be technically more feasible in modular synths that know, for example, how to sequence), because a footstep is a combination of different sounds and may require hand-drawn modulation (i.e. built-in envelopes are not enough, there aren't enough of them or you cannot route them as needed).
The simplest way is to use one synth (or few, if necessary for some reason), use automation as needed and record down different samples. Then edit, treat and piece them together for the finished footsteps. Create new samples when needed. You may also attempt to do most of the sound shaping using MIDI first, i.e. send notes and automate parameters during the note durations, before bouncing down the sounds.
It may seem like it's not going anywhere or you don't know what/how you're going to do it (especially, if you're not very experienced with synthesis), but at some point you should arrive at something that you know how to take it further and how to approach creating new variations. If you're totally stuck: listen to your own foosteps or take a recorded footstep and listen to it, listen to it carefully/analytically. Then proceed to copy it using synthesis. The footsteps that you do may also end up sounding totally crap, but that might be educational for understanding the limits (and exponential complexity, when attempting to model real world sounds) of sound synthesis.
Some reading, if you're interested:
A. Farnell: Designing Sound http://mitpress.mit.edu/books/designing-sound
This book has actual synthesis models, made in Pd.
