I always hear music in my head when I'm in the shower. Or mowing the grass. No joke. Or sometimes I have a certain kind of song I just really want to write, such as "Why don't I have an Yngwie ripoff song? All the other neoclassical fans do," or, "A really metally guitar duet would be sweet."
Usually I get a riff or melody with a chord progression. Then I think "Okay, do I want to keep this mood, switch it up a bit? If I were listening to this song, what would come next to make it awesome!" and try to think of what I would like to hear in this particular song.
And I'm a big fan of intro-verse-chorus-verse-chorus-solo-chorus-outro... it works great! Make sure you don't deny it just to be "progressive" - it's so common because it works so well. Shit, a ton of Symphony X's stuff is like that, with a slow section before the solo, the solo section is a key/guitar duel, and crazy unison right after the key solo... Smoke and Mirrors, Evolution, Fallen, Damnation Game, Orion, they all pretty closely follow this structure.
Lyrics... I'm not too big on lyrics. Most of my stuff that I make on my own is instrumental, and the stuff with my band has lyrics written by our singer, mostly.
I love writing solos. I just improvise over the rhythm parts for the solo section like a million times, until I can do it without thinking about it. Then I eventually get things like a beginning I really like, and a lick that works really well with it, and keep building and keeping the things I like, and throwing away the crap. Usually takes me about a month of playing the song before I have a solo I play the same every time.
Good thread. Makes me wanna go write a song, since I just pretended I knew what I was talking about concerning songwriting for a whole post.