CAT has to do with the type of cable. All it says is whether or not a particular cable is SUITABLE to be used for ethernet at a particular speed. For example, you can run 10mbit ethernet over CAT3 no problem. It has to do with the physical construction of the cable, interference, etc. Basically a rating of how "good" the cable is. The higher the cat # the more speed it will do, or longer distance, etc.
RJ45 is the type of connector on the end. Other RJ connectors include RJ14, which is the kind of connector on most telephones.
In order for a cable to work with ethernet, it has to be wired a certain way. Technically, each end must follow a certain colour order, that takes into account splitting pairs to prevent crosstalk. However, as long as both ends are wired the same, it will *work*, maybe not at full speed, though. Crossover cables are wired slightly differently, with the TX and RX pairs swapped around. There are two different colour orders. IIRC, they are TIA568-A and -B. A crossover cable uses -A on one end, -B on the other, and striagt-through cables generally use -B on both ends.
-B is:
white/orange orange white/green blue white/blue green white/brown brown
You can pretty much assume that any cable sold as CAT5e RJ45 will work for Ethernet. However, it is possible to wire a CAT5e cable to RJ45 plugs in such a way that it will not work with Ethernet. I don't know why anyone would sell such a cable *on it's own* pre-wired, though. Cisco ships (or at least used to, it has been a while since my classes, and I haven't touched a Cisco since) "rollover" cables with their routers, which are used for configuring them with a serial console. They won't work for Ethernet, even though they are CAT(5? 5e? I don't remember) cables with RJ45 plugs on the ends.
If it says something like 1000Base-T, that means it is specifically wired using the proper cable and plugs to do the specified kind of ethernet. In that case, gigabit over twisted pair.
