According to the CCNA Official Guide a switch learns the new MAC address by checking the source MAC address of a new frame. Here is the quote:
Switches build the address table by listening to incoming frames and examining the source MAC address in the frame. If a frame enters the switch and the source MAC address is not in the MAC address table, the switch creates an entry in the table. That table entry lists the interface from which the frame arrived.
And then the CCNA again gave this picture as an example:
So, let's assume that Fred sends a packet to Barney. Switch takes the frame, check it's MAC address table and realize that the sourca address of the frame is not there so it adds it with the interface. But it doesn't know where the destination address is. So how does switch find the path to the correct interface to send the frame? Does it send a broadcast so according to the answers it adds the new MAC's to it's MAC address table according to the source MAC's of replies?