What was the mystery of the lost shoes of Sir Henry Baskerville?
Stapleton required a belonging of Henry's in order to train the hound to attack and kill him. Stapleton was a distant relative, a Baskerville with his eye on Henry's property. He had similarly killed the previous Baskerville who had been living there. So he stole one of Henry's boots to use to train the hound. But it didn't quite work because the boots were new and the hound didn't pick up Henry's scent well. Ironically, Stapleton was still attacked by the hound.
In Ch. 4 Sir Henry Baskerville reports to Sherlock Holmes that one of the boots which he had recently bought and not worn by him even once, had been stolen when he had left the boots outside his hotel room to be cleaned.
"I put them both outside my door last night, and there was only one in the morning. I could get no sense out of the chap who cleans them. The worst of it is that I only bought the pair last night in the Strand, and I have never had them on."
"If you have never worn them, why did you put them out to be cleaned?"
"They were tan boots and had never been varnished. That was why I put them out."
Next, in Ch.5 Sherlock Holmes and Dr. Watson visit Sir Henry at his hotel. As they climbed up the stairs, they saw Sir Henry furiously berating the hotel staff because one of his old boots was now missing:
"Seems to me they are playing me for a sucker in this hotel," he cried. "They'll find they've started in to monkey with the wrong man unless they are careful. By thunder, if that chap can't find my missing boot there will be trouble. I can take a joke with the best, Mr. Holmes, but they've got a bit over the mark this time."
"Still looking for your boot?"
"Yes, sir, and mean to find it."
"But, surely, you said that it was a new brown boot?"
"So it was, sir. And now it's an old black one."
"What! you don't mean to say?"
"That's just what I do mean to say, I only had three pairs in the world -- the new brown, the old black, and the patent leathers, which I am wearing. Last night they took one of my brown ones, and to-day they have sneaked one of the black."
The mystery of the missing boot or boots is explained to us in Ch.15 by Holmes who tells Dr. Watson that Stapleton had stolen the boots so that the murderous hound which he had trained could sniff the boot and get acquainted with the scent of its victim Sir Henry Baskerville and then later kill him. Stapleton had to steal a boot the second time because the first one was new and had not even been worn once by Sir Henry Baskerville, so the hound would not be able to identify its victim by sniffing the new boot whereas the 'old black boot' which had been worn by Sir Henry Baskerville would prove useful for the hound to identify Sir Henry Baskerville by his scent and kill him:
It was very essential for Stapleton to get some article of Sir Henry's attire so that, in case he was driven to use the dog, he might always have the means of setting him upon his track. With characteristic promptness and audacity he set about this at once, and we cannot doubt that the boots or chamber-maid of the hotel was well bribed to help him in his design. By chance, however, the first boot which was procured for him was a new one and, therefore, useless for his purpose. He then had it returned and obtained another -- a most instructive incident, since it proved conclusively to my mind that we were dealing with a real hound, as no other supposition could explain this anxiety to obtain an old boot and this indifference to a new one.
While staying in hotel henry keot his new pair of shoes outside his room for polishing. Afterward one of it was missing.