Phase-detect autofocus sensors are basically tiny, simple rangefinders — light from each side of the lens is split into two paths, and the two paths are projected onto small linear sensors. The difference between the pattern of light and dark is analyzed, and the amount of front or back focus instantly calculated. (That's why phase-detect autofocus is so much faster than contrast-detection as implemented in most point & shoot cameras — with that, the lens has to seek back and forth to find the point of most contrast.)

If you've used a manual-focus camera with a split-prism in the center of the focusing screen, you can recognize same basic principle at work. As with that, the pattern you're focusing on has to be conveniently aligned against the direction of the split prism for it to be of any use.

A cross-type sensor is simply two linear sensors crossing each other (making a cross shape), which is superior because it can work with both vertical and horizontal light patterns.

In manual split-prism focus aids, it's common to align the split diagonally. This conveniently works with both horizontal and vertical lines/patterns. Some Canon cameras use a diagonal cross for their center sensor. There's other possibilities as well: the Sony A700 uses multiple crossed sensors in a # hash configuration.

Apparently some high-end SLRs use a rectangular autofocus sensor which basically is a small, low-resolution copy of the whole image — more like focusing with a real rangefinder camera, automatically. (Wikipedia tells me this is called "Area SIR", for "area secondary image registration".) That's out of my price range, though.

And, it's worth noting that different sensors can have different sensitivities — more sensitive ones work more precisely at wider apertures, with the trade-off being that they don't work as well with lenses limited to slower apertures. That's covered by a whole different question and answer.