Go here:
http://www.spore.com/
And download the free creature creator. I have spent hours making creatures already and I just got it two days ago. It's sort of like making people in the Sims 2, except it can be almost anything you want.
When the actual game comes out in a week it's going to be awesome, and I'm pretty sure the creatures you design will show up in the worlds.
Anyone else making these? Here are all the critters I have made so far: http://www.spore.com/sporepedia#qry=srch-lemonet