On the phone it always defaults to searching the online store/music, instead of the local songs.

The Mac app version is less annoying in that way as it seems to vaguely remember what you were looking at.