A redo works the same way redo works in most non-game software (e.g., text editors and drawing programs), or like how the "forward" navigation button works in a web browser. Undo moves backwards in history, and redo moves forward in history. The player performing an undoable action causes that action to be inserted at the current point in history and all future history to be erased. It's really useful for times when I accidentally undo too many times and want to quickly get back to a future state without having to manually perform the same actions again.
Patrick's Parabox is a good example of a sokoban game with a redo button.