Making a walking robot is another unique challenge that can be tackled with Mindstorms. The above picture is a set of legs I built, adapting a design I saw in this book.
I explain how the above system works in this video:
The other important concept to keep in mind as you design a walking robot, is COG; or center of gravity. Because only one foot of your robot will be on the ground at a given time, you'll either need to find a way to shift the COG over a single side, or you'll need to alternate the leg placements on either side, allowing for a successful walk, devoid of awkward falls and lurches.