Open the Verizon Messages app, swipe from the left edge of the screen to the right to open the Options menu. Tap Search (at the top of the menu), then enter your search text. Search results are displayed below the search box.