Originally Posted by Zomar

Yes, It's important to use GREASE on the threads. Here's a video of how to replace them: http://bicycletutor.com/replace-pedals/

I'm pretty sure lube is different from grease. You want to put on grease to prevent the pedal from seizing to the crank, so that it's easy to remove if you ever need to take the pedal off. Lube is used to reduce friction thus letting things move past each other easier, I don't think that's what you want.