I have a motherboard that supports dual channel DDR2 667Mhz slots with support for up to 4GB.

Will I have to put in 2 sticks with each running at about 667Mhz or will I have to have 2 sticks with each running at about 333Mhz to add up to that 667Mhz?

All of the ram will run at the full speed.

Or, to flesh that answer out a bit, you are meant to use sticks of DDR2-667 MHz RAM, with at least one stick per channel. If you go with 4 GB of RAM, then half the sticks in one channel and half in the other. Similarly for 2 GB. But if you have 3 similar sticks, add the third by all means to a channel - the controller will use it.
Best is if your sticks are matched. eg all DDR2-667 with similar timings.
If you use faster RAM, say DDR2-800 then the BIOS will normally adjust the Memory Strap ratio so that memory transfer rate matches FSB data transfer rate. For the same dollars, 667 RAM may well perform marginally better than 800 RAM because of tighter internal RAM timings. We're talking 1 or 2% here...