The ability to search private messages is not part of the core application that FlyerTalk runs on and was made possible thanks to a third-party plugin. Unfortunately, the plugin had to be disabled, as it didn't function properly when updates were made to search recently.
We'll be on the lookout for alternative options. In the meantime, the best way to search your PMs is to export them as text - if you scroll down to the bottom of your PM inbox you will see this option. Once you export to text, you can open that file in any text editing application (Word, Notepad, etc) and use the application's "Find" feature.
This is a workaround, but can be useful.