A minor update for the Notes app was rolled out earlier in the day. It included the much needed search capability. There is a limitation however. You can only search notes that are already stored in your device. Notes stored in the server but not synced with your device won’t show up in the results (this will be fixed soon).