Miller served on the EAS Agamemnon under John Sheridan in the 2250s. In 2261, Miller served on the Agamemnon under Captain James. That year, he became injured from a fight against raiders near Io and went to Earth to recover.
John Sheridan knew the crew and asked about them from James during his visit. Since he mentioned Miller, Sheridan must have known him from when he served on the ship.