It's different every time for me, really. But what I mainly seem to do is just come across a line, a sentence, something just arrives in my head. Like David Lynch says, it's a lot like fishing, ideas are like bait, you leave it out there and then something else bites, and then something else, and so on and so forth, until you have something.
Sometimes the 'thing' that arrives in my head won't be suitable for a chorus, so I'll simply write it down as the first line to a verse. That way I lead into the song lyrically with the theme that made me write it in the first place.
It's a weird thing, writing a song. I love how we all seem to have our own ways.