It depends on whether or not you want to face wild pokémon. If you don't it's like 50%, if you do it's like 5%. >_<
Ok for the reality: It depends on where you are. Each area has an "encounter rate" assigned to it. I'm not sure of the exact relation between the number and the actual chance. It could be percentage per step, or something completely different. What I do know is the higher the number, the more often you find wild pokémon. I also know that the Safari Zone has the highest of all encounter rates.
The archived version of Pokémon Forever has this information on it.