In Order of the Phoenix, Snape eggs on Sirius at Grimmauld Place:
‘Tell me, how is Lucius Malfoy these days? I expect he’s delighted his lapdog’s working at Hogwarts, isn’t he?’ [Sirius]
‘Speaking of dogs,’ said Snape softly, ‘did you know that Lucius Malfoy recognised you last time you risked a little jaunt outside? Clever idea, Black, getting yourself seen on a safe station platform ... gave you a cast-iron excuse not to leave your hidey-hole in future, didn’t it?’
Order of the Phoenix - Chapter twenty-four, Occlumency - Page 460 - Bloomsbury
How did Lucius Malfoy know that Sirius was a dog Animagus? How did he know it was Sirius in the train station?
Some facts to consider: According to the Harry Potter Lexicon's timeline, the characters who are considered to be of the Marauders era (born 1959) were only five years younger than Lucius Malfoy (born 1954), so Sirius and Snape, and the other Marauders-era students, and Lucius Malfoy, would have been at Hogwarts together for two years. Prisoner of Azkaban demonstrates it took Sirius, James, and Peter four to five years to master the Animagus transformation, which would have been at least two years after Lucius Malfoy would have left Hogwarts (Although we don't know when Lucius became a school governor.).
A canon-based answer would be great; barring one, a speculative answer in the spirit of canon is welcome.