To the people who can't do them:
You're missing a key piece of how to focus properly. People aren't explaining to you what makes them work, so you're not understanding what you need to do in order to see the images. Magic eye pictures are basically a printed version of same trick that makes 3D movies or TVs work. It's also a similar idea at work when you see those holographic cards. The holographic cards have bumps on them so when you move them left right (if the bumps are vertical) you will see the different 'faces' of the bumps with the different strips of whatever image on it. It ultimately gives the impression that there is movement because there are 'frames' printed in each bump's face (frames like in animation). You'll notice when you bend a piece of paper with this stuff on it, all the images blend together and you see pieces of different points of the animation simultaneously.
Now, how it applies to Magic Eye... you need to 'see past the image' not in the figurative sense... you should literally have your eyes focused as if you're looking at something physically behind the image. It's easy on a computer screen, take your finger, focus on it, and then move it behind your computer monitor while maintaining the focus.
The effect will be such that the image on the monitor appears to 'double'. If you cross your eyes hard enough, you can see the entirety of the same image, twice, but through each eye. The trick is that in order to make the images appear, you only want to cross your eyes just enough (aka: look/focus only so far beyond the image) so that the two images overlap correctly to produce the 3D effect. Photoshop COULD produce the 3D image, but without the understanding of how they're made, you'd have a hard time reverse-engineering one to get the 3D image behind it.
It actually helps to have an idea of what you're looking for in the image, too. Your eyes don't always properly discern the illusion at first (this is why knowing that you have to look past the page to a specific point is helpful... sometimes you have to look more or less shallowly behind the image in order to focus correctly). When I'm first looking at an image, it can take a while because I can only discern pieces of it at a time, but eventually I figure out the entire thing.
magiceye.com has a bunch of sample images if you guys would care to check them out. They also have solutions attached for confirming if you saw the right thing.