The job can be as easy/difficult or cheap/expensive as you want to make it. Basically it's down to what rim you want.
I just relaced my first wheel and with a bit of research with youtube how-to's and Sheldon Brown's guide to wheel building I managed to get it absolutely spot on with no special tools other than a spoke key.
For the rim, well, it depends on whether it's 700c or 27", steel or alloy and what you want it to look like. Old chrome 27's come up from time to time on eBay but command good money if they're in good condition, polished alloy ones will start to dent the bank account. Old style looking 700c's are also quite difficult to find and will be more expensive than a new style anodised alloy wheel.
If you're not fussed what it looks like then a new wheel is probably your cheapest bet. The hub should fit the width as they have spacers you add or take off to suit.
This eBay seller has some reasonable priced wheels. £35 for a new polished 27": http://stores.ebay.co.uk/shacklewell-components