The stray dog is a part of a random encounter situation and usually disappears as soon as you leave the cell in which he spawns. Additionally, if you encounter the dog and he dies or you encounter him and don't tell him to go home, the game thinks you still have a animal follower. Don't try to use the stray dog for a pet with the Hearthfire expansion either, he will likely eventually disappear or be extremely bugged. Use Meeko or Vigilance as a pet instead (if you want a dog for Hearthfire).
There is a fix for this bug, however, it requires that Meeko (the dog found at Meeko's Shack) is still alive. Travel to Meeko's Shack (it is just off the main road between Dragon Bridge and Fort Snowhawk) and tell Meeko to follow you. Once he starts following you, dismiss him. This should clear the bug and should allow you to recruit another animal as a follower.
Note: The stray dog encounter is reoccurring and as mentioned previously, you will need to dismiss the stray dog everytime you come across him in the future to avoid this bug. Sometimes you are not even aware that the stray dog has spawned nearby, so this bug is often unavoidable. The fix mentioned above is repeatable (as long as Meeko stays alive) in case you become unable to recruit an animal follower again.