If the daycare man says "They prefer to play with other Pokemon" then the two Pokemon will not breed. If he says anything else then they will breed but it may take longer. Every 256 steps there is a chance an egg might appear, which depends on the species and original trainer.
- Same species, different OT = 69.3%. Message: "The two seem to get along very well."
- Same species, same OT OR different species, different OT = 49.5%. Message: "The two seem to get along."
- Different species, same OT = 19.8%. Message: "The two don't seem to like each other."
So the way to get eggs more quickly is a Ditto from another game. If you can get one from another country (e.g. a European copy of the game if you're in the US) then that also slightly increases the chances of a shiny appearing (but still very rare).