Even with my hands, voice-search on Apple TV, including the YouTube app, is very capable and accurate.
Only if you happen to only search for English titles. Try to search for a foreign song in English (say, La Marseillaise), and the results quickly become next to useless.