There are patterns/designs out there for every level of skills. They are pretty easy to find too, if you just do a google search with something like "beginner cross stitch patter" your bound to find some good free ones.
To start a project you need "Aida cloth" That's the fabric that has a large basket weave texture to it. Made just for cross stitching, pick the lowest number you can find. It will be something like 6 or 8, those are best for beginners. You can usually find it right next to the Embroidery Thread, which you will also need. Sometimes it is call Embroidery Floss, but they are the same thing. It doesn't come on a spool like sewing thread but rather in a skein like yarn, but much smaller lol. It is good to buy the basic colors, if you don't know what you'll be making. Like white, black, brown, grey, plus colors like blue, purple, red, orange, yellow and green. If you find a pattern you want to make though just buy those colors that you'll need :) While your shopping pick up a pack of Embroidery Needles, look like regular needle but have a bigger eye and dull tip, get Size 22 or 24. And also a Embroidery Hoop, I would go for about a 6 inch hoop, that's a good versatile size.
Here is a good site I just found, that explains the basics pretty well and has some free patterns to try out.