Wikipedia actually has an article dedicated to this phrase. It says:
The earliest confirmed publication is the 1866 Dion Boucicault play Flying Scud in which a character knowingly breezes past a difficult situation saying, "Excuse me Mr. Quail, I can't stop; I've got to see a man about a dog." In a listing for a 1939 revival on the NBC Radio program America's Lost Plays, Time magazine observed that the phrase is the play's "claim to fame".
- The most common variation is to "see a man about a horse".
- Almost any noun can be substituted as a way of giving the hearer a hint about one's purpose in departing.
- The inversion to "see a dog about a man" eliminates any lingering uncertainty about whether the hearer is being put off.
- A shorter variant is to "see a man".
As to the exact situation in which you would use this phrase, it suggests:
Used as an excuse for leaving without giving the real reason (especially if the reason is to go to the toilet, or to have a drink)
Back to Wikipedia again,
During Prohibition in the United States, the phrase was most commonly used in relation to the consumption or purchase of alcoholic beverages.
World Wide Words has additional info:
This has been a useful (and usefully vague) excuse for absenting oneself from company for about 150 years, though the real reason for slipping away has not always been the same. [...] From other references at the time [around 1866] there were three possibilities: 1) [the speaker] needed to visit the loo [...] 2) he was in urgent need of a restorative drink, presumed alcoholic; or 3) he had a similarly urgent need to visit his mistress.
Of these reasons [...] the second became the most common sense during the Prohibition period. Now that society’s conventions have shifted to the point where none of these reasons need cause much remark, the utility of the phrase is greatly diminished and it is most often used in a facetious sense, if at all.