Mostly, titles show up with characters and stories for me. I rarely have to hunt for a title or work at it.
That said, I've been working off and on on my Rome novel for six months now, and the top of the first page still says The Rome Novel, and I haven't an inkling what to call it.
Remember: There's lots of really awful titles out there, some of them attached to good books. You won't sink or swim based on title alone. (Or else, books with titles like Her Thundering Passion, or Too Wicked To Wed would never sell)