Looking down at the fretboard there is very little visual reference. Yes the guitar may have fret markers such as pearl inlay dots. Aside from those, a location of a certain string and fret looks exactly like another location of a string and fret. Unlike the piano which is completely coded by a repeating pattern of key shapes and key colors, there is simply no concrete visual reference on the guitar. I think this is the reason why many guitarists, even some very good ones, do not have the notes memorized.
There are two important aspects to learning the notes: One is memorization techniques. Yes, learning the natural notes first is a good one. Try learning all of the locations of each notes, such as learn all of the E's, then all of the A's, etc. Another technique is to memorize a string at a time. Learn the E string, and since there are two E strings you have just conquered 1/3 of the problem.
The second part of learning the fretboad is learning the musical theory and definitions of the layout. We tend to think that string 5 (A) fret 4 is a completely different phenomena from string 2 (B) fret 14. We have to stop thinking this way. Those two place are related. Every two place on guitar are related. If we learn the relationships between notes, and understand the relationships on the fretboard, it will be far easier to remember the notes.
The relationships between the notes, the distance between notes, is called the intervals. Arius mentioned octaves and that is a very important interval. Learn the definition of these first. An octave is two notes 12 half-steps apart. Do not count the starting note as this is a "distance between the notes". The Wikipedia article "Interval (music)" is a good start. Learn the general name (example: major) and the specific name (example: third). Then memorize the note letters for each interval. For example, G to B is a major third. A to C# another. You can spend one to two weeks on each of the intervals. Do not rush this. Once you learn the definitions, then play these intervals all over the fretboard. For example play G then B everywhere. Then play A and C# everywhere, etc.
Once you understand that these intervals are movable patterns that can be played all over the guitar, remembering the notes will come to you.
John C. Boukis
Author: Memorize The Guitar Fretboard