For those times when obvious choices don't come to mind, I'll key off of the bass line, or comping figures (guitar, piano, etc.), as much (if not more than) the melody.  If no particular musical direction comes to mind, I'll start with something very basic and sparse, and build from there (or stay there, if it works).

I'll also try and keep textures in mind.  A beat that has eighth notes in the hi-hat and 2&4 on the snare drum will have a different character if the two parts are played on snare drum with brushes or "hot rods."  (Airto is one of my inspirations in terms of using different sounds and textures on the drum set, BTW - seeing his "Listen And Play" instructional video was revelatory for me.)

What I've found to be very helpful, in terms of developing the ability to come up with a part that fits and embellishes the music (and this is speaking not just as a drummer, but as a vibes player, a percussionist, and as a composer/arranger), is to listen critically to other recordings, and analyze how one player's part relates to the rest of the ensemble.  If the part is unusual, note how it fits against everything else, and that may help you to come up with your own unique parts to fit a given situation.  Or, if the part is very simple, listen to hear if there's something going on in the other parts that would have been covered up by, say, busier or more syncopated drumming.  Over time, this helps to develop one's own abilities in terms of making creative choices, whether those choices are analytical or instinctive in nature.

Drummers who come to mind as I type this include Steve Gadd, Manu Katche, Steve Jordan, Steve Smith (among many, many others) - drummers who have the facility to play very busy (and often complex) parts, and sometimes they opt to do just that - but other times, they'll play very sparsely, and/or very simply.  What was it that prompted Manu to play one way on Peter Gabriel's "In Your Eyes" and "Come Talk To Me," but play another way entirely on "Sledgehammer" or "Steam"?  Ditto for Steve Gadd - I can't think of a better example of a unique drum part that fits perfectly, than "50 Ways To Leave Your Lover," but on another Simon tune (say, "Train In The Distance," on the Central Park concert - I don't recall if Gadd played it on the CD), his part is a very simple, beautiful groove.

If you can try and glean some ideas from these drummers' wonderfully musical decisions, hopefully it'll inform your own ability to do so when you're faced with the challenge of finding the right thing to play on a given song.

IMHO, etc.

Amen to that!

Since my band The Luna Moth is in essence a "jam band" (although that term has such negative connotations to my ears) I'll try different things.  Usually whatever chord progression we are jamming out suggests something to me.  I take feedback from other two guys in the band.  If something doesn't "feel" right, or a change of dynamics or maybe a tighter approach with the bass player...that sort of thing.
Sometimes I'll start playing an odd, angular beat that suggests a vibe to other guys and they arrange their groove to me.  The Luna Moth has a song we've been playing for a year now that we've demoed for our next album called "Black Vinyl Bag" that was written around a circular, Glen Kotchke-esque drum pattern I was fooling around with.  In typical Moth style it is one chord for sometimes 15 minutes.  

As a songwriter on my own more "pop" oriented material I usually have a drum part in my head when I'm writing the song.  I rarely change the part in-between the conception and the actual realization (usually through one-man band multitracking) of the song but sometimes I opt for drum programming rather than tracking drums.  

Imagineering is my approach. It takes quite a few iterations before I/we settle on a groove because the tunes evolve and with each performance everyone is trying to do the same (i.e find 'their own groove"), thereby altering the previous variant.

I think the question ... "How do you find the right groove for a tune?" is the million dollar question.  

To sum up my approach, I do what I feel sounds and works best for the music. There are so many options available, so it all comes down to what I'm wanting to say musically.

In my clinics, I demonstrate how do to this by taking a simple tune, which I've recorded without drums, and proceed to show the hundreds of different approaches, grooves and styles that I could use ... and the rest of the band doesn't change a thing.

Not only the coming up with the groove, but the feel of the tune is another part of the creative journey. Deciding where exactly to place that backbeat, for example ... then putting it there every time ... that's another thing to flesh out.

The more you expose yourself to a WIDE range of music styles, rhythms and genres, the more vocabulary you have to work with, and the more you have to draw from while creating.

I'm coming up with a part to fit what is already going on, I'm naturally going to be influenced by what I hear from the other parts. Sometimes I will instruct others to alter their parts slightly in order for my idea to work. If I'm the one building the foundation first, then the sky is the limit.

hmmm.

looks like the link doesn't work. i think it's not allowed.

go to vinniecolaiuta.com and go to the articles section. it's the first article at the top of the list.