First: Solving the cube likely needs more RAM than what's available in the Arduino. Thus, you need to find a computer that you can interface to your robot actuators, either using direct interface (like a serial bus, for example,) or by talking to a microcontroller which in turn talks to actuators.
Second: You need to design the actual gripper that will hold the cube. There are a minimum number of degrees of freedom you need here; while you can probably just clamp the bottom row in a tightener, you need the other arm to articulate in three rotational degrees, plus have a gripper, plus have an in/out degree of freedom.
Third: You need a way to "read" the cube. This would require a webcam or similar, hooked to your computer. OpenCV is a fine library to use to interface with webcams for robotics.
Fourth: Find a rubik's cube solver program that is open source on the Internet. Build it and examine the code to make sure you understand how it works.
Five: Tie all the software together such that you first take a picture of all six sides of the cube (moving it with the arm,) then let the solver program calculate the solution, then execute the solution by moving the arm/cube.
These are each a pretty meaty challenge, but they are all doable (you can google for various images and videos of robots that do this.)
If you want to write your own solver, then you should build a representation of the problem space using six surfaces with 3x3 colors, with an interconnectedness graph of how the different manipulations solve the cube, and then run a planner/search algorithm (a breadth-first search might eventually terminate, but uses a lot of RAM -- you can probably do better with directed search.)
That should give you terms to google for -- "breadth first graph search" and "forward planning algorithm" would be great starts.
