iPhone OS 3.0 introduced Spotlight Search: Flick to the left and you can search through the apps you have installed as well as other things like contacts, calendars events, emails, songs and notes.
For apps the iPhone OS will look at the app name that you see under it’s icon. So typing ‘bird’ would find the Birdfeed app.
But the OS also looks at the name of the app as it appears in iTunes. Birdfeed’s name in the app store is “Birdfeed - A very nice Twitter client”, which is why Birdfeed shows up when you type ‘twitter’.

When you download an app to your phone the .ipa file includes the actual app binary as well as an iTunesMetadata.plist file. This plist file contains the app’s name as it appears in iTunes.
Tweetie on the other hand doesn’t show up in the screen-shot above even though it is installed on the phone. Tweetie’s name in the app store is “Tweetie 2″ which doesn’t include the word ‘twitter’.
