Cyclo-X has been around since the 1940's and was originally a way for road racers to maintain their fitness level through autumn and early winter. It started in Europe where it has remained consistently popular. In belgium it is almost a religion and Belgium is infact often referred to as the home of Cyclo-X.
Cyclo-X has very close connections with Mountain Biking, though obviously cross came first. If you look at world class mountain bike races from the early-mid '90s onwards, Europeans won almost all the races. It's not because they picked up on mountain bike racing more quickly than the Americans who 'invented' mountain biking, it is because of their background in cyclo-x. Several mountain bike world champions in recent years have also been past cyclo-X champions.
Fitness and Skills
Cross racing requires a combination of mountain biking and road racing skills and of course a reasonable level of fitness. The races are short, so endurance is not that critical, however the constant switching between aerobic and anaerobic modes means you need a different type of endurance; the capacity to hurt for a full 60 minutes. The ability to run, or at least to sprint for a few dozen yards, is useful, and if you don't have the riding skills to control a skinny-tyred bike on slippery surfaces, you will after only a few races.
Having a go
Almost all cross races allow mountain bikes as long as they don't have forward facing bar-ends. These are banned because of safety concerns during a crash. Most beginners will first try cross on a mountain bike due improved stability. However, many accomplished cross racers will always ride a mountain bike, while others sometimes ride a mountain bike depending on the course and conditions.
The best way to understand cyclo-x is to go and watch a race. Make sure to take your bike so you can ride the course before the first race starts. Looking at a cross course is always confusing at first because they are typically set up with ribbons and flags, which serpentines over a relatively small area. Once you ride the course and then watch a race you will understand all.