How did Saruman know who Gimli was ?

[Inziladun]

Originally Posted by Sarumian

I don't think he knew anything about Gimli before the Fellowship departed from Rivendail. However he could have learnt it either from his spies in Hollin (there could be not only animals, but Dunlendings), or from Wormtongue, or himself in Farngorn, as have already been said here, so there was no mistake.

I doubt Dunlendings, or any other two-legged spies, could have been close enough to the Company in Eregion to have overheard their speech.
For one thing, the lands surrounding Rivendell had been well searched prior to the departure of the Fellowship. Also, it seems likely anyone trying to follow them would have been marked by Legolas, Aragorn, or Gandalf at least, not to mention the Hobbits, who were sharp enough to see and hear Gollum later on when he was on their trail.

And by the way, welcome Sarumian!