An enigma wrapped in a puzzle
A step-by-step solution of a sample nonoriddle can be found here.
Solving a nonoriddle basically requires two parts: Completing the grid-based fill-in-the-squares puzzle (similar to a puzzle that goes by various names, such as Nonogram®, Paint By Number®, Griddler®, Logic Square, "Japanese Crossword", etc.) and then determining the solution out the revealed riddle.
The numbers at the edge of the grid represent how many squares in a row to fill in for that row or column. These groups of squares are always separated by at least one empty square and are in the same order as the numbers at the edge. For example, one of the rows might read as follows:


or this:

Or one of several other combinations. Note that the group of four and the group of three cannot be right next to each other (otherwise it'd be a group of seven); at least one empty square always will separate a group. From this, several methodologies can be deduced to solve the puzzle. Some of these are shown in the walkthrough (link on the left) and Wikipedia has an excellent description of advanced solution techniques here.
When all the filled-in squares in a nonoriddle grid have been marked, the remaining letters reveal a riddle. Reading left to right, top to bottom reveals all the letters needed to assembled the riddle. The location of spaces and punctuation need to be inferred based on context. The solution to the riddle is a single word. Since even a crossword clue can have multiple solutions without crossing words, a few rules have been given to help determine the correct solution.
With these three rules, the answer to the riddle can be narrowed to a single word. In the "Naturally black and white and read all over" example, we know that we're looking for a word that begins with "N", ends with "R", is nine letters long, and has something to do with lining a birdcage. So while the answer to the riddle by itself could conceivable be "literate zebra", the three rules show that it has to be "newspaper".
Click here to view a walkthrough of a sample nonoriddle.