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.