It's supposed to be at the bottom of the screen when you're looking at all the conversations. Maybe it's a bug. Some other people had a similar issue with the search bar in Contacts.
I always use the Search button on the home screens right below the last row of icons...it searches your whole phone (if you have the search settings enabled to do that). Its always been able to search for particular words or whatever in iMessage...at least for me.