A set of stainless spokes and nipples will cost you a bit over $100 for each wheel and it will cost you about the same amount to have it laced and trued. You can do it yourself of course, its not difficult, and the cost of the tools you'd need is only about as much as you'd pay to have someone do one wheel, around a hundred bucks. You'd need a spoke wrench, a dial indicator and mounting clamps and such, and some sort of stand to hold the wheel.
After its been laced and any protruding spoke ends cleaned up you put a "rim strip" on it. That is the large rubber band that goes around the wheel's center to protect the tube that will be used from rough metal. They cost two or three bucks and can be had from just about any motorcycle shop. As for the tire, you can put it on anytime you like, the wheel won't care.