Every 256 steps, the game will decide if an egg is produced. When the man says they seem to get along, there is a 50% chance an egg will appear.
So an egg can appear after 256 steps, or 512 or so on. You are almost certain to get an egg after 1024 steps.
In D/P/Pt you are best cycling up and down the looong road in Solaceon Town. You can also see when you pass the daycare if there is an egg - f the man is looking towards the road then there is an egg!