IIRC, it uses a database of common and popular songs stored locally on your phone (possibly adapted to what Google knows about your taste in music, idk) and only goes online for matches when you do a manual song search.