Do you have the latest update or even 3rd gen iPod?
You can search for anything on it by sliding your app page to the page just before your first app page. you can even set to what you want it to only search in the settings.
was looking for something inside the music app but guess that doesn't exist. using spotlight is fine with me, i just didnt want to have to exit out and go back in, etc.
I don't know about previous versions of the OS, so you may want to make sure you're up to date (3.1.3) but in my iPod app all you have to do is scroll the page down and the Search bar will reveal itself on top.