You have to let the Gondolier sing all of the songs from the jukebox outside the weapons shop
1. have bozo meet his woman for the first time, the Gondolier will sing a song
2. Shut down the power generator powering the tavern (use the sugar dispenser you get in the tavern on it), use the screwdriver on the jukebox and you'll see a sleeping man, take the sheet music he has on the stand in front of him, go outside and place the music on the Gondoliers stand.
3. go back to Bozo and ask him to try again. the Gondolier will sing a different song (but to the same rhythm)
4. go back to the tavern and change the song with the jukebox (the man will either swap the paper in front of him or pull up a new piece of paper), then go shut down the generator again and come back to the tavern, take the music that was replaced
Do steps 2 to 4 going through all of the songs in jukebox that the Gondolier hasn't played in front of the weapons shop