data Piece = X | O
means that X and O are constants, having data type 'Piece'.
In other words, you directly use X and O instead of Piece X and Piece O.
Piece is a type, and X and O are constructors (or simply the two possible values).
A good similar example is the Bool type,
data Bool = False | True
-- Two possible values, i.e. False and True
Also, to make life easier, you might want to use:
data Piece = X | O
deriving Show -- Make this type showable
With this, you will be able to use 'print' with elements of this datatype.
For updating nested lists, you have to create a function that takes two numbers (the positions) and iterates over the whole structure, just updating the required position.
While this may seem like an overkill, it gets optimized by ghc.
I don't have any experience with lenses, but they should be usable here. Understanding them will require a good understanding of the type system.