Not a lot of information is widely available for pneumatic cylinders and the Arduino (or at least none that I have found, please leave a comment if you know of anything other than a simple demo project). There are a couple of projects I found on YouTube but a lot of them never went very far or are just the basics (which I can use to get started).
I hope to change all of that by releasing all the entire project as Open Source/Open Hardware for anyone to recreate, and/or modify.
I live in a small apartment on Long Island, NY and so I have a few neighbors with only a small paper-thin wall between us. So my work will have to take place at reasonable hours of the day (ie: 5pm-8pm on weekdays, 12pm-8pm on weekends). This will prevent me from doing a lot of hardware testing late at night (my best coding time, as I am sure you are familiar with) and will slow down my progress. I am employed by a company that is about 10min. away from my apartment, and as a small company I wear quite a few hats and tend to work more than 40hrs/week, so my rate of progress will probably be slower than I would have liked. That being said, this project is going to take months if not years so I am OK with this as it allows me to reflect on what I have accomplished that day, and allow me to update this project log.
So a lot of walking gaits for robots are so called: static movement algorithms, in which the robot is always balanced, but that is not how we walk, so I will choose the active dynamic movement algorithms (Passive dynamic movement uses the inertia of the robot to make the walking gait), which I will have to write myself.
My control program will need some sort of feedback to get the right "muscle memory" to stand up and walk, which will probably be some sort of potentiometer along with an accelerometer(already have) and gyroscope, since it is cheaper than a flow meter and/or some sort of position sensor.
This HackADay article on hacking a laser measurement system might be valuable for determining distance to objects and/or the ground, which will probably provide useful for control.