I'm currently building a robot with four legs (quadruped), 3 DOF (Degrees of Freedom) and Its been suggested here that I use a simulator to do the learning on a computer and then upload the algorithms to the robot. I'm using an Arduino Uno for the robot and what software could I use to simulate the learning and then be able to upload to the Arduino board?
Gazebo is a good tool for what you want to do. Since you're using a custom robot you will need to build a model for the simulator to use. They have managed to make doing so pretty easy but for a quadraped I can imagine it will take a bit of time.
Gazebo is also nice because it works well with ROS which means that if you build you could build a program to control your robot and send the commands to the simulated robot via the integration or to the real robot via rosserial. Just beware that if you have not used any of these tools then it will take some time to develop your solution.
This wouldn't cover the robot simulation, but the OpenCV Machine Learning Library might be useful for evaluating learning algorithms and training parameters to download to the robot.
It includes a neural network implementation, which may be of particular interest for this problem.
OpenCv is a standard library too, and would likely integrate well with some other simulator for the robot itself.
The recently open-sourced V-REP simulator may suite your needs. I found it more approachable than Gazebo, and it can run on Windows, OSX, and Linux. Their tutorials are fairly straight forward. There are a ton of different ways to interface with it programmatically (including with ROS). It looks like there is even a tutorial for making a hexapod, which you could probably use as a starting point if they don't already have a quadruped example available. Unfortunately, I believe the simulator is tied directly with the UI rendering, which I believe is not necessarily the case with Gazebo.
So, your program would have to use one of the many ways to interface with V-REP, and then feed the performance of a particular gait, determined from some sensor in V-REP, into a machine learning algorithm (perhaps something from OpenCV as @WildCrustacean mentioned). You'd then have to come up with a translation from the gait description used by the simulated robot to something used to command actual motors on your Arduino.
On the other hand, you could make your own simulator using an existing physics engine, rendering it with a graphics library. Bullet and OGRE, respectively, could be used for this purpose, if you like C++. There are tons of others for other programming languages.
I would also look into how researchers who work on gait generation do their simulations. There might be an existing open source project dedicated to it.