To unlock the following songs, you must complete certain worlds then select the song from the song selection list by pressing Y and shifting the song lists all the way to the left.

Theme	How to unlock
Bicycle Theme (Gold/Silver)	Complete Calypso Beach (World 3)
Champion Theme (Red/Blue)	Complete Sleighbell Mountains (World 5)
Pokemon Gym Theme	Complete Marching Hills (World 1)
Route 26 Theme (Gold/Silver)	Complete Rock Range (World 2)
Trainer Battle Theme (Black/White)	Complete Baroque Valley (World 7)