I want to know this too...not necessarily for Starred, but a regular playlist. I just put all my music in the same playlist, so i have 2500+ songs in one playlist...being able to search is imperative!
I don't think there is a way right now to search within playlists, which is interesting because you can do it on every other platform. But the app did just come out. Maybe they'll add it in an update soon. That would be very nice, as I have very long playlists...
It's very disappointing that they have yet to implement this feature on the iPad. More screen real estate, but somehow less features and options than its iPhone/iPod siblings.
EDIT: They just released updated iOS apps with a radio feature, but guess what? Still no filter or search within playlist option. :(
