Yeah, you need to master JQL to be able to find anything. Once you do that however (and once it's configured properly) Jira is actually quite enjoyable to use. I had a couple of episodes with other issue trackers and I always missed Jira.
And since we are complaining about search feature I must mention Confluence. Like I've said you can query Jira with JQL but in Confluence you're out of luck.
Yeah, JQL is the key, and they do a good job with suggestions and completions in the query editor. One of the few parts of the Jira UI that I actually think works pretty well.