You are about to enter the wonderful world of Charcuterie, the preserving and curing of meats.
The traditional cut of beef to turned into corned beef (or pastrami, which has a similar preparation) is a well-marbled brisket. I'd imagine that a flank steak or other similar long-and-moist cuts would work out too.
The curing process involves soaking the brisket in a brine of pickling spices (for flavor) and Sodium Nitrite, which will preserve (cure) the meat and provide that wonderful pink color. You'll have to plan ahead, as the process takes about five days. I've used the recipe detailed in this forum post with fantastic results before. I think that it comes from this book, which you might think of picking up if you have future dreams of sausage, pastrami, and other feats of meat.