Starting over means restoring your current game to the way it was at the very beginning, before you had made any moves. When you start over, you lose all the moves you have made so far.
You can also use the Undo All feature to rewind to the beginning of your game. This is like using Start Over, except that with Undo All you will see all your moves rewind backwards, and you will still be able to Redo the moves you made if you choose to. With Start Over all your previous moves are forgotten, and you cannot Redo them.