What brand of pedal are you using? I've had this problem with my current Look pedals. I've tried greasing the pedal where the cleat contacts it, I've tried cleaning the pedals and cleats really well and running them without grease- you name it, I've tried it. The only thing that consistently works is to put new cleats on. Then all's well for a while until they start to wear. It's driving me crazy because there's no rhyme or reason to when they will start sqeaking. They started up out of the blue a few weeks ago during a race. Very annoying to be sounding like a 4-year-old riding my tricycle in a race.

My solution is that I'm switching to Speedplay Zero's as soon as the budget permits. Short of that, I'd recommend new cleats, and don't walk on them (use the plastic cleat covers).

My pedals are also look pedals - how expensive are new cleats?

First try removing the cleat cleaning the contact area and scewing them back on...

otherwise the cleats are about 12 dollars...

This squeaking is especially bad if they are worn... indicated by the presence/absence of the wear indicators (round indentations at the three points of the cleat)

I found a great solution to the look pedal squeak. ski wax. I use glide wax that I use on my skate skis. I crayoned it on the front and back edges and the front tongue of my cleats, heated it up a little and no more squeak. It lasts several rides, but i always reapply before really long group rides so I don't get killed by my riding partners. It goes on a little better after the cleats are roughened up a little either from use or with a little very fine sandpaper.