I just started and finally caught my second Pokémon, as I noticed these steps on my close by Pokémon. What does it mean? It is probably related with how far the Pokémon is, but how far is far?
Note: As of Pokemon GO version 0.29.1 or so, the "footprint" indicator was disabled, and all Pokemon are three footprints away. This is a known bug, and the fault of Niantic Labs (and the server overload as a result of the game's popularity.
Note 2: As of Pokemon GO Version 0.30.1, the Footstep indicators have been removed. The game will show all Pokemon within 200 meters of your current location, with the nearest being anywhere in the list.
These steps represent the distance from the Pokemon currently.
Each footprint represents 50 meters of distance, starting with zero footprints means the Pokemon is no more than 50 meters away.
For example, one footprint means the Pokemon can be 51-100 meters away in any direction. Three footprints means the Pokemon is at most 200 meters away.
Note, however, that these numbers do not reflect Pokemon spawned through Incense or Lure Modules. Additionally, there is (at the time of writing - version 0.29.0) a bug that causes the distances to not update properly, causing the approximate values to be slightly "off."