Robotics is a bit outside of my wheelhouse, but this is how I'd approach it:
1. Decide what sort of behavior you want. At the simplest, it could be how fast it can move forward. The more (mathematically) precise you can state the objective the robot is trying to achieve the easier and faster it's going to be to get there.
2. Decide what sort of inputs you have to your learning algorithm. You have the inputs from the sensors, of course, but you could also store inputs from the recent past and feed those in. At the very least, you almost certainly have some sense of time based on the update frequency of the various components, or at the least the clock rate of the microcontroller. You can also do things like multiply one sensor's input by another's input to get a nonlinear third input. The "magic" in neural networks is basically this sort of non linear behavior.
3. Figure out a training regiment. Are you simulating the robot in a virtual environment first and then uploading the resulting model to the robot? Or do you want the robot to figure it out on its own? (That's cooler, but will take a small eternity most likely, and is certainly more difficult).
4. From the answers above, you can figure out an appropriate machine learning method. Basically you want to find a "model" that will produce the right outputs given the right inputs, which is a machine learning problem. Essentially you're producing something like a big (probably sparse) matrix that maps inputs (including the non linear inputs I mentioned) to outputs.
A genetic algorithm makes a lot of sense if you can "parameterize" your model. So for instance, it's quite good at finding the right values for leg length, contraction force, contraction frequency, etc. if you were simulating a frog learning to jump. I'm not a huge fan of neural networks, but they can be useful if you need to capture some nonlinear behavior (like do something in relation to the product of two other things). (Most of what I don't like about them is that they obfuscate the underlying math behind a facade of being a "brain", when in point of fact biological brains are way more complex and sophisticated and doing way more interesting math).
...
My main piece of advice would be to abandon biologically-inspired learning algorithms, and see what else you have available to you. At the end of the day, neural nets are just nonlinear best-fit curves in high dimensional space, genetic algorithms are just some sort of stochastic gradient ascent for an optimization problem, etc. The underlying math is all that really matters, so I would explore things on that front. Of course I'm pretty math heavy as a person. If you don't feel as comfortable with linear algebra, you might not want to explore too far off the beaten path. Just figure out what your inputs and outputs look like, and how you can measure success and failure, and look around the machine learning literature and see if you can find an algorithm that makes sense.
But there's nothing wrong with starting with a genetic algorithm or a neural net if that inspires you
