There are a number of things to consider for your project. Since you are asking for the learning algorithms, I asume your hardware is or will be up and running. When getting your robot to learn, you should differentiate between on-line and off-line learning. Further, there is on-system and off-sytem learning, which can be combined with the previous category. Since your system only has a micro-controller attached to it, your method of choice would be off-system. You learn (be it on-line or off-line) on your connected PC, but not on the system. The system will just execute your current learned policy.
All gait movements have some sort of cyclic nature, and can generally be described as functions that provide an angular value over time for each of the joints. The trick is to parametrize these functions that you come out with as little parameters as possible. Then you perform optimization on these functions. In order to do that you need to know what to optimize for.
Most learning approaches will require some sort of reward function, so effectively some feedback to the algorithm to tell it how well it does perform (e.g. maximise distance travelled/energy required). The algorithm will then want to see the reward for a given set of parameters (single episode). Depending on the complexity of your problem, the number of episodes might be quite large. This is where the destinction between on-line and off-line learning comes in. In off-line learning you use a simulation to perform the learning and then later move it to the system. In on-line learning you learn directly on the system. This is generally more difficult, since you will have to spend a lot of time performing evaluations for the learning algorithm.