You should really use at least Cat5E grade cable, not just plain Cat5, as the Cat5E is rated for gigabit connections, while plain Cat5 is only 100Mbps. They cost about the same so you might as well use the better cable rather than having to worry about upgrading it in the future. If you stream media between your PC, laptop and PS3 gigabit will be slightly better.
I'd actually recommend using Cat6 as the cost difference between Cat5E and Cat6 is nearly nothing (in my neck of the woods anyway) although if you're crimping it yourself it can be a bit harder to work with due to the slightly thicker cable.
Both Cat6 and Cat5E are rated for gigabit with Cat6 being slightly more robust, its doubtful you'll see any difference between the two in a home environment. Cat6A is rated for 10 gigabit which hasn't really hit the consumer sector yet so you can forget about that for now.
I wouldn't go to the expense of STP, standard UTP (unshielded twisted pair) cable is fine for home use. Ethernet is pretty robust against interference anyway. Even so, you should avoid running your network cables right next to power cables. If you have to cross them do so at a perpendicular angle. You should also avoid running your cables near flourescent lighting.
Having said that, I've seen plenty of installations that broke both the above rules and still functioned perfectly, using UTP.
As has been said, make sure all your cables are wired the same way on either end. If you wire a cable with 568A on one end and 568B on the other that's a crossover cable, used for connecting two PC's or two switches together. For all cabling in the walls and between an end-user device and a switch/router use normal straight through cables.
For the wall plates you'll want a KRONE punch down tool. And when crimping your own cables, please make sure the plastic outer sheaf is crimped inside the RJ45 connector! there should be no coloured wires visible past the end of the plastic connector. I see people crimp their cables with a gap of up to 2cm between the outer sheaf and the RJ45 connector... its dodgy as hell, so don't do it
