The advent of touchscreens provides a new opportunity for effectively learning layouts. My method of learning was:
Use the colemak layout extensively on mobile device. After 1-2 days, this provided me with "look and thumb" muscle memory.
Switch to computer with guide image. Due to "look and thumb" memory, my lookup speed was very fast. Within 1-2 days the image even became unnecessary, and I basically knew (within a few seconds) where to press any letter.
The rest proceeded as normal: practice to turn this location knowledge into purely finger-muscle memory.
The main advantage to adding a step 1 is that it splits the learning process into easier parts. If one starts with 2, one'd simultaneously be learning a) where to lookup letters, b) how to translate this to finger presses. Having to learn two disjoint practices at once is generally slower and (to me, at least) much more frustrating. Better to start with the intermediate touchscreen where the lookup gives you immediate results (1/a), then only transition once proficient at this (2/b).
Edit (25/4/12): note that, for QWERTY touchtypists, Tarmak can provide an even more gradual method of switching.