tl;dr: This is gonna be a lengthy one :-)
My suggestion
My suggestion would be to start with the pentatonic aeolean (minor) pattern over the whole fretboard - the most natural one on the guitar would be the A minor scale or E minor also aligns pretty nice with the tuning and the markers.
My approach is to get used to the basic fret positions and then gradually combining the sections of the scale until you have gained the muscle memory to play the scale by heart. After this there are many other interesting scales that deviate somehow from the common pattern found in church modes (oriental scales with 1/4 steps come to mind or maybe if you're a freak like me you start looking into parallel galaxies).
Edit
Just to be clear: this is not a tutorial to become a good musician - see the other answers - but merely a guide to memorizing scales. So go now and take on music theory and play to your favorite songs to get a feeling for it. If you want to know how I learned the modes keep on reading.
Muscle memory
This is the process of how I trained my muscle memory to learn the minor modes:
Here is the pattern for A minor that neatly aligns with the fret markers - I'm right handed but you can mirror the pattern vertically to match your guitar:
E || x | | | x | | O | | | x | | x | || x | | | x | ...
B || | x | | x | | x | | | x | | O | || | x | | x | ...
G || x | | O | | | x | | x | | x | | || x | | O | | ...
D || x | | x | | | x | | O | | | x | || x | | x | | ...
A || O | | | x | | x | | x | | | x | || O | | | x | ...
E || x | | | x | | O | | | x | | x | || x | | | x | ...
Fret 0 1 2 3 4 5 6 7 8 9 10 12
Dot . . . . . ..
Phase1 -=============-
Phase2 -=============- -=============-
Phase3 -=========- -==================-
Phase4 -===============================================================-
Xs mark notes that belong to the scale; Os mark the root note of the scale (A in this case). Notice that the pattern repeats itself along the fretboard after 12 frets (half steps). If E minor suits you more you only need to shift the whole pattern down 5 frets (to the left).
The phases
When I began looking into scales I would find the root note at the 5th fret on the low E string and work my way up the strings in this fret position (frets 5 - 8, strings E - E). The next fret position to add is the 12th fret (or an octave lower starting with open low E). The final step for the pentatonic is connecting the known fret positions and practicing transitions all over the fretboard.
Going further
When you feel comfortable playing it, to the point where you just need the root note and the rest flows from the heart without looking too much or at all at the fretboard, you can begin to gradually add the missing 3-note-per-string notes. If you're into the blues this would also be a good place to explore the blue notes.
Here is the scale filled up with the missing notes (+) to make a full aeolean minor mode - note that the new notes are all 6 half steps (a diminished 5th) apart:
A aeolaen (minor):
E || x | + | | x | | O | | + | x | | x | || x | + | | x | ...
B || + | x | | x | | x | + | | x | | O | || + | x | | x | ...
G || x | | O | | + | x | | x | | x | + | || x | | O | | ...
D || x | | x | + | | x | | O | | + | x | || x | | x | + | ...
A || O | | + | x | | x | | x | + | | x | || O | | + | x | ...
E || x | + | | x | | O | | + | x | | x | || x | + | | x | ...
Fret 0 1 2 3 4 5 6 7 8 9 10 12
Dot . . . . . ..
Fun fact: if you take the inverse of the full scale (e.g. the notes not marked) its a pentatonic scale again namely D#/Eb - a wait-for-it diminished 5th lower than A brain-explode.
A aeolaen "inverse":
E || | | x | | x | | x | | | x | | O || | | x | | ...
B || | | x | | O | | | x | | x | | x || | | x | | ...
G || | x | | x | | | x | | O | | | x || | x | | x | ...
D || | O | | | x | | x | | x | | | x || | O | | | ...
A || | x | | | x | | O | | | x | | x || | x | | | ...
E || | | x | | x | | x | | | x | | O || | | x | | ...
Fret 0 1 2 3 4 5 6 7 8 9 10 12
Dot . . . . . ..
Modes, modes, modes
The good thing is that most of the conventional church modes derive from the same pattern only starting at a different note (there are some minor modifications with melodic minor, gypsy scales etc.). So I solely need to memorize one scale and can play all the others from that. Personally, I started too late with the other modes so the minor is pretty much engraved into my head and I still need to think too much to switch modes. So remember to practice all modes from the beginning.
Here are some diagrams for constructing the church modes out of the A minor scale. Note that the root note is wandering up the common scale pattern. If you wanted to play A phrygean you would need to shift the whole scale to get the root note to A (e.g. E|0 -> E|5 for phrygean) :
E phrygean:
E || x | + | | x | | x | | + | x | | x | || O | + | | x | ...
B || + | x | | x | | O | + | | x | | x | || + | x | | x | ...
G || x | | x | | + | x | | x | | O | + | || x | | x | | ...
D || x | | O | + | | x | | x | | + | x | || x | | O | + | ...
A || x | | + | x | | x | | O | + | | x | || x | | + | x | ...
E || O | + | | x | | x | | + | x | | x | || O | + | | x | ...
Fret 0 1 2 3 4 5 6 7 8 9 10 12
Dot . . . . . ..
Root x
F lydian:
E || x | O | | x | | x | | + | x | | x | || x | O | | x | ...
B || + | x | | x | | x | O | | x | | x | || + | x | | x | ...
G || x | | x | | + | x | | x | | x | O | || x | | x | | ...
D || x | | x | O | | x | | x | | + | x | || x | | x | O | ...
A || x | | + | x | | x | | x | O | | x | || x | | + | x | ...
E || x | O | | x | | x | | + | x | | x | || x | O | | x | ...
Fret 0 1 2 3 4 5 6 7 8 9 10 12
Dot . . . . . ..
Root x
G mixolydian:
E || x | + | | O | | x | | + | x | | x | || x | + | | O | ...
B || + | x | | x | | x | + | | O | | x | || + | x | | x | ...
G || O | | x | | + | x | | x | | x | + | || O | | x | | ...
D || x | | x | + | | O | | x | | + | x | || x | | x | + | ...
A || x | | + | x | | x | | x | + | | O | || x | | + | x | ...
E || x | + | | O | | x | | + | x | | x | || x | + | | O | ...
Fret 0 1 2 3 4 5 6 7 8 9 10 12
Dot . . . . . ..
Root x
A aeolaen (minor):
E || x | + | | x | | O | | + | x | | x | || x | + | | x | ...
B || + | x | | x | | x | + | | x | | O | || + | x | | x | ...
G || x | | O | | + | x | | x | | x | + | || x | | O | | ...
D || x | | x | + | | x | | O | | + | x | || x | | x | + | ...
A || O | | + | x | | x | | x | + | | x | || O | | + | x | ...
E || x | + | | x | | O | | + | x | | x | || x | + | | x | ...
Fret 0 1 2 3 4 5 6 7 8 9 10 12
Dot . . . . . ..
Root x
B locrian:
E || x | + | | x | | x | | O | x | | x | || x | + | | x | ...
B || O | x | | x | | x | + | | x | | x | || O | x | | x | ...
G || x | | x | | O | x | | x | | x | + | || x | | x | | ...
D || x | | x | + | | x | | x | | O | x | || x | | x | + | ...
A || x | | O | x | | x | | x | + | | x | || x | | O | x | ...
E || x | + | | x | | x | | O | x | | x | || x | + | | x | ...
Fret 0 1 2 3 4 5 6 7 8 9 10 12
Dot . . . . . ..
Root x
(Locrian mode seems not to be very common these days due to the missing perfect fith but I like it and I despise leaving things out so I learned it anyways)
C ionian (major):
E || x | + | | x | | x | | + | O | | x | || x | + | | x | ...
B || + | O | | x | | x | + | | x | | x | || + | O | | x | ...
G || x | | x | | + | O | | x | | x | + | || x | | x | | ...
D || x | | x | + | | x | | x | | + | O | || x | | x | + | ...
A || x | | + | O | | x | | x | + | | x | || x | | + | O | ...
E || x | + | | x | | x | | + | O | | x | || x | + | | x | ...
Fret 0 1 2 3 4 5 6 7 8 9 10 12
Dot . . . . . ..
Root x
D dorian:
E || x | + | | x | | x | | + | x | | O | || x | + | | x | ...
B || + | x | | O | | x | + | | x | | x | || + | x | | O | ...
G || x | | x | | + | x | | O | | x | + | || x | | x | | ...
D || O | | x | + | | x | | x | | + | x | || O | | x | + | ...
A || x | | + | x | | O | | x | + | | x | || x | | + | x | ...
E || x | + | | x | | x | | + | x | | O | || x | + | | x | ...
Fret 0 1 2 3 4 5 6 7 8 9 10 12
Dot . . . . . ..
Root x
Like I said that's the way I learned the scales but I hope this helps anyone to get started.
Just one more ...
As a side note: if one day you wish to play an instrument that has more than the default 6 strings the pattern above gets more complicated but this is only due to the standard tuning - with the odd major third between G and B to make playing chords easy I guess. If you look at the pattern in all perfect fourths tuning (raising B->C and high E->F) you'll see that it's the same thing over and over again to infinity so adding new strings is a almost a no brainer :-). So for soloing the following tuning could come in very handy as it does for me at the time of writing:
A aeolaen (minor):
F || + | | x | | O | | + | x | | x | | x || + | | x | | ...
C || x | | x | | x | + | | x | | O | | + || x | | x | | ...
G || x | | O | | + | x | | x | | x | + | || x | | O | | ...
D || x | | x | + | | x | | O | | + | x | || x | | x | + | ...
A || O | | + | x | | x | | x | + | | x | || O | | + | x | ...
E || x | + | | x | | O | | + | x | | x | || x | + | | x | ...
Fret 0 1 2 3 4 5 6 7 8 9 10 12
Dot . . . . . ..
Root x
Look how regular and beautiful this is :-)