Last week when Sean, Ralph, Lori, Eli, and I were hanging out together, someone raised the question of how the snake got around in its pre-slither days. (According to the Torah, the snake has to crawl on the ground as punishment for luring Chava to eat the fruit from the tree of knowledge.) I said that I was certain there's midrash on the subject, but I couldn't summon the knowledge at the time. I finally ended up asking a rabbi at Ohr Somayach (who provide a very friendly and helpful question-answering service).
Ok, here's the answer: according to Rashi (one of the leading commentators), the snake used to have legs but they were taken away as part of the curse. (So no, the snake wasn't "walking" on its tail or some such.) Rashi cites Midrash Rabbah (20:5), which I haven't a clue how to look up.