While in Cloud City, C-3PO is shot by a stormtrooper, torn into pieces, and thrown in the trash. Chewbacca finds all of his parts, narrowly saving him from the incinerator. How in the hell did Chewbacca know to look there? The time between their arrival at Bespin and capture by Vader was hours, at best. How did Chewbacca know that C-3PO was missing, and how did he find him so quickly?
Chewbacca followed his nose, literally.
From the script, it's clear that Chewie is surprised to smell burning droid (after C-3PO gets shot) but shrugs it off as being part of the station's normal scents. When they realise that the droid is missing, he rightly puts the pieces together and goes searching for that same smell:
A laser bolt to Threepio's chest sends him flying in twenty directions. Smoldering mechanical arms and legs bounce off the walls as the door whooshes closed behind him.
Lando, Han, and Leia continue down the corridor unaware of Threepio's dreadful accident. Chewbacca glances around, sniffs the air, but shrugs his shoulders and follows the group.
The novelisation also backs this up
Some distance away, Lando guided the small group into his hall of offices, pointing out objects of interest as they moved through the white corridors. None of them had noticed Threepio’s absence as they walked along, discussing life in Bespin.
But Chewbacca suddenly stopped and curiously sniffed the air as he looked behind him. Then he shrugged his huge shoulders and continued to follow the others.
Chewbacca, who had grown concerned about See Threepio, slipped away from Han Solo and the others and began hunting for the missing droid. All he had to follow were his keen Wookiee instincts as he wandered through the unfamiliar white passageways and corridors of Bespin.
Following his senses, Chewbacca finally came upon an enormous room in a corridor on the outside of the Cloud City. He approached the entrance to the room and heard the clamor of metallic objects clattering together. Along with the clanging, he heard the low grunting of creatures he had never encountered before.